Narrow Results

We give some connections between various functions defined on finitely presented groups (isoperimetric, isodiametric, Todd–Coxeter radius, filling length functions, etc.), and we study the relation between those functions and the computational complexity of the word problem (deterministic time, nondeterministic time, symmetric space). We show that the isoperimetric function can always be linearly decreased (unless it is the identity map). We present a new proof of the Double Exponential Inequality, based on context-free languages.

This contribution wishes to argue in favor of increased interaction between experts on finite monoids and specialists of theory of computation. Developing the algebraic approach to formal computations as well as the computational point of view on monoids will prove to be beneficial to both communities. We give examples of this two-way relationship coming from temporal logic, communication complexity and Boolean circuits. Although mostly expository in nature, our paper proves some new results along the way.

We prove new results about the remarkable infinite simple groups introduced by Richard Thompson in the 1960s. We give a faithful representation in the Cuntz C^⋆-algebra. For the finitely presented simple group V we show that the word-length and the table size satisfy an n log n relation. We show that the word problem of V belongs to the parallel complexity class AC¹ (a subclass of P), whereas the generalized word problem of V is undecidable.

We study the distortion functions of V and show that V contains all finite direct products of finitely generated free groups as subgroups with linear distortion. As a consequence, up to polynomial equivalence of functions, the following three sets are the same: the set of distortions of V, the set of Dehn functions of finitely presented groups, and the set of time complexity functions of nondeterministic Turing machines.

We study the algorithmic complexity of determining whether a system of polynomial equations over a finite algebra admits a solution. We characterize, within various families of algebras, which of them give rise to an NP-complete problem and which yield a problem solvable in polynomial time. In particular, we prove a dichotomy result which encompasses the cases of lattices, rings, modules, quasigroups and also generalizes a result of Goldmann and Russell for groups [15].

By the fundamental theorem of symmetric polynomials, if P ∈ ℚ[X₁,…,X_n] is symmetric, then it can be written P = Q(σ₁,…,σ_n), where σ₁,…,σ_n are the elementary symmetric polynomials in n variables, and Q is in ℚ[S₁,…,S_n].

We investigate the complexity properties of this construction in the straight-line program model, showing that the complexity of evaluation of Q depends only on n and on the complexity of evaluation of P.

Similar results are given for the decomposition of a general polynomial in a basis of ℚ[X₁,…,X_n] seen as a module over the ring of symmetric polynomials, as well as for the computation of the Reynolds operator.

We prove the following two results announced by Rhodes: the Type II subsemigroup of a finite semigroup can fall arbitrarily in complexity; the complexity pseudovarieties C_n (n ≥ 1) are not local.

Stalling's folding process is a key algorithm for solving algorithmic problems for finitely generated subgroups of free groups. Given a subgroup H = 〈J₁,…,J_m〉 of a finitely generated nonabelian free group F = F(x₁,…,x_n) the folding porcess enables one, for example, to solve the membership problem or compute the index [F : H]. We show that for a fixed free group F and an arbitrary finitely generated subgroup H (as given above) we can perform the Stallings' folding process in time O(N log*(N)), where N is the sum of the word lengths of the given generators of H.

We study the algorithmic complexity of determining whether a system of polynomial equations over a finite algebra admits a solution. We prove that the problem has a dichotomy in the class of finite groupoids with an identity element. By developing the underlying idea further, we present a dichotomy theorem in the class of finite algebras that admit a non-trivial idempotent Maltsev condition. This is a substantial extension of most of the earlier results on the topic.

We discuss time complexity of the Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.

This paper shows an algorithm which computes the law of the Lie algebra associated with the complex Lie group of n × n upper-triangular matrices with exponential elements in their main diagonal. For its implementation two procedures are used, respectively, to define a basis of the Lie algebra and the nonzero brackets in its law with respect to that basis. These brackets constitute the final output of the algorithm, whose unique input is the matrix order n. Besides, its complexity is proved to be polynomial and some complementary computational data relative to its implementation are also shown.

We study the monoid generalization M_{k, 1} of the Thompson–Higman groups, and we characterize the - and the -order of M_{k, 1}. Although M_{k, 1} has only one nonzero -class and k-1 nonzero -classes, the - and the -order are complicated; in particular, is dense (even within an -class), and is dense (even within an -class).

We study the computational complexity of the - and the -order. When inputs are given by words over a finite generating set of M_{k, 1}, the - and the -order decision problems are in P. However, over a "circuit-like" generating set the -order decision problem of M_{k, 1} is -complete, whereas the -order decision problem is coNP-complete. Similarly, for acyclic circuits the surjectiveness problem is -complete, whereas the injectiveness problem is coNP-complete.

The Thompson–Higman groups G_k,i have a natural generalization to monoids, called M_k,i, and inverse monoids, called Inv_k,i. We study some structural features of M_k,i and Inv_k,i and investigate the computational complexity of related decision problems. The main interest of these monoids is their close connection with circuits and circuit complexity.

The maximal subgroups of M_k,1 and Inv_k,1 are isomorphic to the groups G_k,j (1 ≤ j ≤ k - 1); so we rediscover all the Thompson–Higman groups within M_k,1.

Deciding the Green relations and of M_k,1, when the inputs are words over a finite generating set of M_k,1, is in P.

When a circuit-like generating set is used for M_k,1 then deciding is coDP-complete (where DP is the complexity class consisting of differences of sets in NP). The multiplier search problem for is xNPsearch-complete, whereas the multiplier search problems of and are not in xNPsearch unless NP = coNP. The class of search problems xNPsearch is introduced as a slight generalization of NPsearch.

Deciding for M_k,1 when the inputs are words over a circuit-like generating set, is ⊕_k-1•NP-complete; for any h ≥ 2, ⊕_h•NP is a modular counting complexity class, whose verification problems are in NP. Related problems for partial circuits are the image size problem (which is # • NP-complete), and the image size modulo h problem (which is ⊕_h•NP-complete). For Inv_k,1 over a circuit-like generating set, deciding is ⊕_k-1P-complete. It is interesting that the little known complexity classes coDP and ⊕_k-1•NP play a central role in M_k,1.

We investigate the computational complexity of deciding whether or not a given polynomial, presented as the sum of monomials, is identically 0 over a ring. It is proved that if the factor by the Jacobson-radical is not commutative, then the problem is coNP-complete.

The main purpose of this paper is to improve the bound of complexity of the well-known algorithms on polynomial ideals having complexities polynomial in dⁿ, where d is the maximal degree of input polynomials and n is the number of variables. Instead of this bound, we present the more accurate bound max{S, Dⁿ} where S is the size of the input polynomials in dense representation, and D is the arithmetic mean value of the degrees of input polynomials.

We prove that in a free group the length of the value of each variable in a minimal solution of a standard quadratic equation is bounded by 2s for an orientable equation and by 12s⁴ for a non-orientable equation, where s is the sum of the lengths of the coefficients.

It is known that the bounded Geodesic Length Problem in free metabelian groups is NP-complete [A. Myasnikov, V. Roman'kov, A. Ushakov and A. Vershik, The word and geodesic problems in free solvable groups, Trans. Amer. Math. Soc.362(9) (2010) 4655–4682] (in particular, the Geodesic Problem is NP-hard). We construct a 2-approximation polynomial time deterministic algorithm for the Geodesic Problem. We show that the Geodesic Problem in the restricted wreath product of a finitely generated non-trivial group with a finitely generated abelian group containing ℤ² is NP-hard and there exists a Polynomial Time Approximation Scheme for this problem. We also show that the Geodesic Problem in the restricted wreath product of two finitely generated non-trivial abelian groups is NP-hard if and only if the second abelian group contains ℤ².

In this paper, we study the basic problem of counting independent sets in a graph and, in particular, the problem of counting antichains in a finite poset, from an algebraic perspective. We show that neither independence polynomials of bipartite Cohen–Macaulay graphs nor Hilbert series of initial ideals of radical zero-dimensional complete intersections ideals, can be evaluated in polynomial time, unless #P = P. Moreover, we present a family of radical zero-dimensional complete intersection ideals J_P associated to a finite poset P, for which we describe a universal Gröbner basis. This implies that the bottleneck in computing the dimension of the quotient by J_P (that is, the number of zeros of J_P) using Gröbner methods lies in the description of the standard monomials.

Agol, Haas and Thurston showed that the problem of determining a bound on the genus of a knot in a 3-manifold, is NP-complete. This shows that (unless P$=$NP) the genus problem has high computational complexity even for knots in a 3-manifold. We initiate the study of classes of knots where the genus problem and even the equivalence problem have very low computational complexity. We show that the genus problem for alternating knots with n crossings has linear time complexity and is in Logspace$(n)$. Alternating knots with some additional combinatorial structure will be referred to as standard. As expected, almost all alternating knots of a given genus are standard. We show that the genus problem for these knots belongs to $T{C}^0$ circuit complexity class. We also show, that the equivalence problem for such knots with $n$ crossings has time complexity $nlog(n)$ and is in Logspace$(n)$ and $T{C}^0$ complexity classes.

We prove that the conjugacy problem in the first Grigorchuk group $\mathrm{\Gamma }$ can be solved in linear time. Furthermore, the problem to decide if a list of elements $w_1,\dots ,w_k\in \mathrm{\Gamma }$ contains a pair of conjugate elements can be solved in linear time. We also show that a conjugator for a pair of conjugate element $u,v\in \mathrm{\Gamma }$ can be found in polynomial time.

We give a simple algorithm to solve the subgroup membership problem for virtually free groups given as a graph of finite groups. For a fixed virtually free group with a fixed generating set X, the subgroup membership problem is uniformly solvable in time $O(N{log}^{\ast }(N))$ where N is the sum of the word lengths of the inputs with respect to X. For practical purposes, this can be considered to be linear time. The algorithm is simple enough to work out small examples by hand and concrete examples are given to show how it can be used for computations in $\mathrm{\text{SL}}(2,\mathbb{Z})$ and $\mathrm{\text{GL}}(2,\mathbb{Z})$. We also give fast algorithm to decide whether a finitely generated subgroup of a virtually free group is free.