<p>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 <a href="http://www.jstor.org/stable/3597195" rel="noreferrer">Sapir-Birget-Rips, Annals of Math 2002</a> 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:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2017-03-02T17:25:25.857Z
2017-03-02T17:25:25.857Z
Joshua Grochow
<p>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 <em>polynomial time</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-22T20:44:30.807Z
Also, if someone could stick a group-theory or group related tag on this, I would appreciate it.
Aubrey da Cunha
CC BY-SA 3.0
2011-07-25T17:37:24.510Z
You are correct.  Fixed.
Aubrey da Cunha
<cc.complexity-theory><computability><gr.group-theory>
Do there exist groups with word problems in arbitrary P-degrees?
Aubrey da Cunha
# Do there exist groups with word problems in arbitrary P-degrees?

(Asked by: username_0 on 2011-07-22)

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.

**Tags:** cc.complexity-theory, computability, gr.group-theory
> **Comments:**
> **username_0**: Also, if someone could stick a group-theory or group related tag on this, I would appreciate it.  
> **username_0**: You are correct.  Fixed.  

---

## 1 answers

### Answer by username_1 on 2017-03-02. Score: 6

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](http://www.jstor.org/stable/3597195) 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.


---

