23
$\begingroup$

Are there finitely generated groups whose word problem is solvable, but not quickly? It would be great to have specific examples, but existence results would also be helpful.

All of the groups that I know with solvable word problem (linear groups, hyperbolic groups, branch groups) have a low-degree polynomial time algorithm for solving the problem. I am looking for something between those groups and the ones with unsolvable word problem.

$\endgroup$
  • 9
    $\begingroup$ There are fairly standard constructions that should build fg groups for whom the word problem is equivalent to the membership problem for your favourite subset $S\subseteq \mathbb{N}$. For instance, I think the word problem in $\langle a,b\mid [a^{-n}ba^n,b]=1\Leftrightarrow n\in S\rangle$ can be seen to be at least as difficult as membership of $S$. (Of course, one needs to check that the word problem is actually solvable, but I don't think that's too difficult in this case.) For finitely presented examples, one could invoke Clapham's improvement of Higman's embedding theorem. $\endgroup$ – HJRW Aug 9 '15 at 6:08
19
$\begingroup$

There is a very nice recent paper "Algorithmically complex residually finite groups" by O. Kharlampovich, A. Myasnikov, and M. Sapir about this issue - containing also many references to earlier results about complex Dehn functions and the complexity of the word problem in specific cases.

Theorem (Kharlampovich, Myasnikov, Sapir) Let $f(n)$ be a recursive function. Then there exists a residually finite finitely presented solvable group G such that for any finite presentation $⟨X;R⟩$ of $G$ the time complexity of both “yes” and “no” parts of the word problem are at least as high as $f(n)$.

The paper also contains examples.

$\endgroup$
  • $\begingroup$ I'm confused by the formulation because the word problem depends on a generating subset, not a finite set of relators. $\endgroup$ – YCor Dec 29 '16 at 6:49
  • $\begingroup$ @YCor; the obvious algorithm for the "yes" part uses $R$ as an input. $\endgroup$ – Andreas Thom Dec 29 '16 at 11:58
  • $\begingroup$ I have checked the linked paper. Your formulation is misleading and I think you don't really answer the question. It's not the complexity of the YES/NO parts of the word problem: it's the efficiency of 2 precise algorithms to solve them, namely those that are known to hold in every finitely presented residually finite group (with a given finite presentation) (YES by enumerating relation iterating relators, NO by testing all finite quotients). $\endgroup$ – YCor Dec 29 '16 at 15:01
  • $\begingroup$ For instance, for a finitely presented subgroup of a direct product of free groups, there is an obvious highly efficient algorithm for the word problem. But it might be that even for such groups these two precise algorithms (especially the YES one iterating relators - by this I mean enumerating elements in the normal subgroup generated by relators). $\endgroup$ – YCor Dec 29 '16 at 15:04
  • $\begingroup$ @YCor But the formulation in the paper is identical to the one given by Andreas Thom, and Theorem 4.19 of the paper certainly seems to state that we can choose $G$ to have "hard" but solvable word problem. So if you are right, then it is the paper that is very misleading! $\endgroup$ – Derek Holt Dec 29 '16 at 17:03
5
$\begingroup$

Here's a recipe to produce f.p. groups with solvable word problem at least as hard as the membership problem in any set $A$ of positive integers.

Consider the group $$\Gamma_A=\langle t,x\mid [t^nxt^{-n},x]=1, \forall n\in A\rangle.$$

Then for $n>0$, $[t^nxt^{-n},x]=1$ in $\Gamma_A$ iff $n\in A$. In particular, ($\#$) any algorithm for the word problem in $\Gamma_A$ with complexity $f(n)$ (supremum of halting time for inputs in the $n$-ball) solves the membership problem in $A$ with halting time $\le f(4n+4)$.

The group $\Gamma_A$ has solvable word problem iff $A$ is recursive. So for finitely generated group we are already done with no prerequisites (of course this boils down to the question of complexity of the membership problem in recursive subsets integers, but this is no longer group theory).

Now an adaptation of Higman's embedding theorem by Clapham (C. R. J. Clapham. An embedding theorem for finitely generated groups”, Proc. London. Math. Soc. (3), 17, 1967, 419-430.) yields that every f.g. group with solvable word problem embeds into a finitely presented group with solvable word problem. If we embed $\Gamma_A$ into such a finitely presented group $\Lambda$ and require that $t,x$ are among a generating subset, then ($\#$) above also holds in $\Lambda$.

The case of residually finite finitely presented groups is considerably harder and is addressed by the Kharlampovich-Myasnikov-Sapir paper referenced in Andreas Thom's answer.

$\endgroup$
  • $\begingroup$ By the way, assuming it's classical, I'd be curious of references about hardness of the membership problem of recursive subsets of integers. Is it true that for every recursive function $f(n)$, there exists a recursive set of positive integers such that for every algorithm solving membership to $A$, the supremum $g(n)$ of halting times for all inputs $k\le n$ satisfies $g(n) \gg f(n)$? $\endgroup$ – YCor Dec 29 '16 at 17:50
3
$\begingroup$

A likely example is given by Cremona groups, as in this paper by Serge Cantat (I suspect Yves Cornuiller will comment...)

$\endgroup$
2
$\begingroup$

I know you didn't ask for it, but the most natural example for my money of a countably generated group would be the colimit of the alternating groups $A(2^k)$, unioned along the inclusions $A(2^k) \to A(2^{k+1})$ given by $\sigma \mapsto ((x, b) \mapsto (\sigma x, b))$. You can think of this group as permutations of infinite bitstrings which fix cofinitely many bits.

The generating set is given by taking any family of reversible universal gates and allowing each one to act on any appropriately sized subset of the infinitely many bits. Here, deciding the word problem amounts to deciding whether the circuit represented by a given word is the identity, which is coNP complete.

EDIT: Turns out this example can be squeezed into a finitely generated group. See this paper for a group which is finitely generated with coNP complete word problem, obtained by constructing a Thompson-like group which contains words that act like circuits.

$\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.