BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Andrey Nikolaev appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group. More generally, we show NP-hardness of that problem in weakly regular branch groups, which implies NP-completeness if the group is, in addition, contracting.
This work explores a structure of the Deprit perturbation series and its connection to a Kato resolvent expansion. It extends the formalism previously developed for the Hamiltonians linearly dependent on perturbation parameter to a nonlinear case. We construct a canonical intertwining of perturbed and unperturbed averaging operators. This leads to an explicit expression for the generator of the Lie-Deprit transform in any perturbation order. Using this expression, we discuss a regular pattern in the series, non-uniqueness of the generator and normalised Hamiltonian, and the uniqueness of the Gustavson integrals. Comparison of the corresponding computational algorithm with classical perturbation methods demonstrates its competitiveness for Hamiltonians with a limited number of perturbation terms.
The classic knapsack and related problems have natural generalizations to arbitrary (non-commutative) groups, collectively called knapsack-type problems in groups. We study the effect of free and direct products on their time complexity. We show that free products in certain sense preserve time complexity of knapsack-type problems, while direct products may amplify it. Our methods allow to obtain complexity results for rational subset membership problem in amalgamated free products over finite subgroups.
We consider several subgroup-related algorithmic questions in groups, modeled after the classic computational lattice problems, and study their computational complexity. We find polynomial time solutions to problems like finding a subgroup element closest to a given group element, or finding a shortest non-trivial element of a subgroup in the case of nilpotent groups, and a large class of surface groups and Coxeter groups. We also provide polynomial time algorithm to compute geodesics in given generators of a subgroup of a free group.
This work explores the structure of Poincare-Lindstedt perturbation series in Deprit operator formalism and establishes its connection to Kato resolvent expansion. A discussion of invariant definitions for averaging and integrating perturbation operators and their canonical identities reveals a regular pattern in a Deprit generator. The pattern was explained using Kato series and the relation of perturbation operators to Laurent coefficients for the resolvent of Liouville operator. This purely canonical approach systematizes the series and leads to the explicit expression for the Deprit generator in any perturbation order: \[G = - \hat{\mathsf S}_H H_i.\] Here, $\hat{\mathsf S}_H$ is the partial pseudo-inverse of the perturbed Liouville operator. Corresponding Kato series provides a reasonably effective computational algorithm. The canonical connection of perturbed and unperturbed averaging operators allows for a description of ambiguities in the generator and transformed Hamiltonian, while Gustavson integrals turn out to be insensitive to normalization style. Non-perturbative examples are used for illustration.
Let $G$ be a non-elementary hyperbolic group. Let $w$ be a group word such that the set $w[G]$ of all its values in $G$ does not coincide with $G$ or 1. We show that the width of verbal subgroup $w(G)=<w[G]>$ is infinite. That is, there is no such $l\in\mathbb Z$ that any $g\in w(G)$ can be represented as a product of $\le l$ values of $w$ and their inverses.
We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete.
We generalize the classical Post correspondence problem ($\mathbf{PCP}_n$) and its non-homogeneous variation ($\mathbf{GPCP}_n$) to non-commutative groups and study the computational complexity of these new problems. We observe that $\mathbf{PCP}_n$ is closely related to the equalizer problem in groups, while $\mathbf{GPCP}_n$ is connected to the double twisted conjugacy problem for endomorphisms. Furthermore, it is shown that one of the strongest forms of the word problem in a group $G$ (we call it the {\em hereditary word problem}) can be reduced to $\mathbf{GPCP}_n$ in $G$ in polynomial time. The main results are that $\mathbf{PCP}_n$ is decidable in a finitely generated nilpotent group in polynomial time, while $\mathbf{GPCP}_n$ is undecidable in any group containing free non-abelian subgroup (though the argument is very different from the classical case of free semigroups). We show that the double endomorphism twisted conjugacy problem is undecidable in free groups of sufficiently large finite rank. We also consider the bounded $\mathbf{PCP}$ and observe that it is in $\mathbf{NP}$ for any group with $\mathbf{P}$-time decidable word problem, meanwhile it is $\mathbf{NP}$-hard in any group containing free non-abelian subgroup. In particular, the bounded $\mathbf{PCP}$ is $\mathbf{NP}$-complete in non-elementary hyperbolic groups and non-abelian right angle Artin groups.
Spinlocks are widely used in database engines for processes synchronization. KGX mutexes is new retrial spinlocks appeared in contemporary Oracle versions for submicrosecond synchronization. The mutex contention is frequently observed in highly concurrent OLTP environments. This work explores how Oracle mutexes operate, spin, and sleep. It develops predictive mathematical model and discusses parameters and statistics related to mutex performance tuning, as well as results of contention experiments.
Rise of hundreds cores technologies bring again to the first plan the problem of interprocess synchronization in database engines. Spinlocks are widely used in contemporary DBMS to synchronize processes at microsecond timescale. Latches are Oracle RDBMS specific spinlocks. The latch contention is common to observe in contemporary high concurrency OLTP environments. In contrast to system spinlocks used in operating systems kernels, latches work in user context. Such user level spinlocks are influenced by context preemption and multitasking. Until recently there were no direct methods to measure effectiveness of user spinlocks. This became possible with the emergence of Solaris 10 Dynamic Tracing framework. DTrace allows tracing and profiling both OS and user applications. This work investigates the possibilities to diagnose and tune Oracle latches. It explores the contemporary latch realization and spinning-blocking strategies, analyses corresponding statistic counters. A mathematical model developed to estimate analytically the effect of tuning _SPIN_COUNT value.