14
$\begingroup$

It has been known for a long time that, given any r.e. Turing degree, there is a finitely presented group whose word problem is in that degree. My question is whether the same thing is true for arbitrary polynomial time Turing degrees. Specifically, given a decidable set, $A$, does there exist a finitely presented group, with word problem, $W$, such that $W\leq_T^P A$ and $A\leq_T^P W$? I would also be willing to relax finitely presented to recursively presented.

I suspect that the answer is yes, and I have heard others say they read this somewhere, but I haven't been able to chase down a reference.

$\endgroup$
  • $\begingroup$ Also, if someone could stick a group-theory or group related tag on this, I would appreciate it. $\endgroup$ – Aubrey da Cunha Jul 22 '11 at 20:44
  • $\begingroup$ You are correct. Fixed. $\endgroup$ – Aubrey da Cunha Jul 25 '11 at 17:37
6
$\begingroup$

I think this is not known. (I apologize - I think I was also one of the people that said I had remembered reading this somewhere.) For example, I believe that Sapir-Birget-Rips, Annals of Math 2002 were the first to show the existence of a group with $\mathsf{NP}$-complete word problem (which would be a trivial consequence of the result asked for in this question). Their Corollary 1.1 states:

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 time complexity of $G$ is polynomially equivalent to the nondeterministic time complexity of $L$.

While the second half of this corollary is kind of in a similar spirit to this question, it is a far cry from proving that every $\leq_T^p$-degree contains a word problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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