# Do there exist groups with word problems in arbitrary P-degrees?

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.

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

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.