22
$\begingroup$

There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).

Then there are several classes of groups like asynchronously automatic groups for which it is known that there is an exponential time algorithm to solve the word problem (and whether this can be improved to polynomial is open and conjectured as far as I'm aware).

Going several steps further, there is an algorithm to solve the word problem in one-relator groups in time not bounded by any finite tower of exponentials (and again it is open and conjectured whether this can be improved to P).

On the other, there are algorithms to solve word problems in pathological groups like the Baumslag-Gersten group:

$$G_{(1,2)} = \langle a, b | a^{a^b}= a^2 \rangle$$

in polynomial time. So even though general algorithms can be very bad, it is unknown whether there are group-specific algorithms for every group in a given class that solve the word problem quickly.

So my question is, are there any groups in which it is known that the word problem (or any other computational problem) is at least exponential, but still solvable? Maybe exp-complete? What are the approaches to proving such a thing?

$\endgroup$
24
$\begingroup$

An earlier reference for groups with this property is

J. Avenhaus and K. Madlener. Subrekursive Komplexität der Gruppen. I. Gruppen mit vorgeschriebenen Komplexität. Acta Infomat., 9 (1): 87-104, 1977/78.

There is a hierarchy of the recursive functions known as the (difficult to pronounce) Grzegorczyk Hierarchy $E_0 \subset E_1 \subset E_2 \subset \cdots$, where (roughly) $E_1$ contains the linearly bounded functions, $E_2$ polynomially bounded functions, and $E_3$ those functions that are bounded by iterated exponentials.

The above paper describes constructions of finitely presented groups $G_n$ for $n \ge 3$, in which solving the word problem has time complexity bounded by a function $E_n$ but not by any function in $E_{n-1}$,

$\endgroup$
  • $\begingroup$ Thanks Derek, this seems to be exactly what I was looking for! $\endgroup$ – MSL Jan 27 at 19:39
19
$\begingroup$

As Andreas says (in his answer and his comment to it), there are groups whose word problem is undecidable and one could similarly set up a group that encodes the halting problem of a class of Turing machines where this is decidable but difficult. However, one must be careful in the encoding. In

Isoperimetric and Isodiametric Functions of Groups, Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips Annals of Mathematics Second Series, Vol. 156, No. 2 (Sep., 2002), pp. 345-466

and

Mark V. Sapir, Jean-Camille Birget and Eliyahu Rips Isoperimetric functions of groups and computational complexity of the word problem. Ann. of Math. (2) 156 (2002), no. 2, 467–518.

groups with NP complete word problem are constructed and other similar results. See in particular, Corollary 1.1 of the first paper listed above.

To add more information, Corollary 1.1 says:

There exists a finitely presented group with NP-complete word problem. Moreover for every language $L\subseteq A^*$ for some finite alphabet $A$ there exists a finitely presented group $G$ such that the nondeterministic complexity of $G$ is polynomially equivalent to the nondeterministic complexity of $L$.

So, for instance, if $L$ is an EXP-time complete problem, then the word problem of $G$ is in NEXP-time and not in NP (hence not in P). Of course you can replace EXP by your favorite time complexity class strictly above NP.

$\endgroup$
11
$\begingroup$

There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .

$\endgroup$
  • $\begingroup$ True, what I really meant was among the groups whose word problem is solvable. Thanks, I'll edit my question! $\endgroup$ – MSL Jan 23 at 17:57
  • 7
    $\begingroup$ @MSL I'd expect that the same method can handle the decidable case. Instead of coding into the presentation a Turing machine whose halting problem is undecidable, code one whose halting problem is decidable but takes a very long time to decide. $\endgroup$ – Andreas Blass Jan 23 at 18:06
6
$\begingroup$

Classical problem which is believed not to be in P is number factoring, which can be cast as computing a decomposition of a cyclic group into simple ones.

Several problems in permutation groups are known to be as hard as graph isomorphism, thus not believed to be in P, too.

There are also NP-hard problems known for permutation groups, see e.g. https://www.sciencedirect.com/science/article/pii/S0012365X09001289

$\endgroup$
  • 1
    $\begingroup$ Checking if a cyclic group is simple would seem to be primality testing which is in P. $\endgroup$ – Benjamin Steinberg Jan 24 at 0:58
  • $\begingroup$ You are right; I have corrected my answer to reflect this. $\endgroup$ – Dima Pasechnik Jan 24 at 1:09
  • 1
    $\begingroup$ As I have mentioned elsewhere, no problem in NP has ever been proven to be outside of P. So problems in NP seem like the exact opposite of what the OP asked for. You need problems complete in a complexity class proven to be separate from P, not just assumed (with good reason) to be separate from P. $\endgroup$ – Yakk Jan 24 at 16:58
  • $\begingroup$ “NP-hard” does not merely mean “in NP”. Roughly, it means “at least as hard as an NP-complete problem”, and NP-complete problems are believed not to be in P. $\endgroup$ – Dima Pasechnik Jan 24 at 17:09
  • $\begingroup$ Yes, it means at least as hard as an NP-complete problem, but you surely see how that doesn't answer the question. NP-hard problems are only conjecturally harder than P. $\endgroup$ – Pål GD Jan 24 at 19:00
1
$\begingroup$

While most other answers have mentioned computational problems related to finitely presented (but generally infinite) groups, there are many problems in finite group theory which are either conjectured or known to be NP-complete. As an example, we have the following result from A. Lubiw, "Some NP-complete problems similar to graph isomorphism", SIAM J. Comp. 10(1981) 11-21.

The problem of determining whether $G$ has a fixed point free element is NP-complete, even for elementary abelian $2$-groups.

The classic problem of determining the number of subgroups of a group of order $n$ is also, as far as I can tell, conjectured to be very difficult, but I am not aware of any definite statement in either direction.

Moving back to the world of finitely presented groups, the subset sum problem is defined as follows. Given $g_1, \dots, g_k, g \in G$, decide whether $$ g = g_1^{\varepsilon_1} \cdots g_k^{\varepsilon_k}$$ for some $\varepsilon_1, \dots \varepsilon_k \in \{ 0, 1\}$. This problem is known to be NP-complete for a vast range of different classes of groups, including, but not limited to, free metabelian non-abelian groups of finite rank, and the wreath product of two finitely generated infinite abelian groups. It is also known to be NP-complete in some particular cases, such as for $BS(1, 2)$ and Thompson's group $F$. In hyperbolic groups, however, the problem is P-time decidable, so the problem certainly is an interesting one.

The subset sum problem and many other related problems for finitely presented groups are studied in detail in A. Miasnikov, A. Nikolaev, A. Ushakov, "Knapsack Problems in Groups", Math. of Comp. 84(2013).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.