10
$\begingroup$

This has been posted on TCS stack exchange for a while here and hasn't gotten any answers, so I'm trying again here.

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.

EDIT: As per the comments, here, $\leq_T^P$ means polynomial-time Turing reducibility. See here for more info.

Improve this question
$\endgroup$
1
  • $\begingroup$ @Aubrey: Presumably, "r.e." stands for recursively ennumerable. For the benefit of those not in the field, you might want to explain the symbol $\le^P_T$. $\endgroup$
    – André Henriques
    Commented Aug 8, 2011 at 23:38

2 Answers 2

Reset to default
7
$\begingroup$

I think the question is also answered positively by the main result in a paper of mine -- Efficient computation in groups and simplicial complexes. Trans. Amer. Math. Soc. 276 (1983), no. 2, 715–727 -- where it is shown that any Turing machine may be simulated by a finitely presented group in linear space and cubic time.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Simulating a Turing machine deciding $L$ in the group certainly gives a reduction from $L$ to the word problem for the group, but is there a reduction the other way? This is the same issue as in Mark's answer. $\endgroup$
    – Aubrey da Cunha
    Commented Aug 10, 2011 at 17:37
7
$\begingroup$

The answer is "yes" (for finitely presented groups). It follows from the main result of Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu Isoperimetric and isodiametric functions of groups. Ann. of Math. (2) 156 (2002), no. 2, 345–466.

Edit. Here is the combination of me explanations in comments below.

You should look at the construction of the group in the paper. First there is a modification of a Turing machine so that the input configurations contribute to the time function the most. Then an S-machine is constructed which by prop. 4.1 is working in polynomial time comparing to the Turing machine and has the same property re input vs arbitrary configurations. Then a group is constructed using the S-machine. Then the Dehn function of the group is estimated (you need the estimate from above). The last step is done by the snowman decomposition. The snowman decomposition decomposes every van Kampen diagram into a linear number of discs and a diagram without hubs (whose area is at most cubic). The perimeters of the discs are linear in terms of the length of the boundary of the diagram. Given a boundary label of a disc, deciding that the disc with this boundary label exists is essentially the same as to decide that certain word belongs to L. Thus the snowman decomposition is a certificate that the word problem is in $L^P$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I took a look at this paper and it appears to give half of what I need. It is pretty clear that Theorem 1.3 in the paper gives a $\leq_1^P$-reduction from any $L$ to some word problem, but it doesn't give a reduction back. For my purposes, knowing that the time complexity of the word problem is essentially the same as the time complexity of $L$ is not strong enough. Are there details in the proof of Theorem 1.1 that give this reduction? $\endgroup$
    – Aubrey da Cunha
    Commented Aug 10, 2011 at 17:27
  • $\begingroup$ @Aubrey: Perhaps I misunderstood the question. What exactly is the reduction from w.p. to languages you need? In the paper, for every language $L$ recognized by a machine, we construct a group that "recognizes" essentially the same language in essentially the same time. But perhaps you need more. If so, then what? Perhaps I can modify the construction. It is quite flexible. $\endgroup$
    – user6976
    Commented Aug 10, 2011 at 21:26
  • $\begingroup$ @Mark: What I need is the word problem constructed to be in $P^L$. Having essentially the same time complexity doesn't give this inclusion immediately. A priori, it's possible that the fastest reduction from the word problem to $L$ could be to decide the word problem (not necessarily in $P$) and output a hard-coded string that is in or out of $L$ accordingly. $\endgroup$
    – Aubrey da Cunha
    Commented Aug 10, 2011 at 22:15
  • $\begingroup$ @Aubrey: I guess I do not quite understand what $P^L$ is (I thought it is exactly what is proved in the paper). I do not have time to google it up. Could you explain? $\endgroup$
    – user6976
    Commented Aug 10, 2011 at 23:06
  • $\begingroup$ @Mark: Certainly. What I mean by $P^L$ is that there is some Turing machine that, when given oracle access to $L$, can compute the word problem in polynomial time. If we have some $L$ not decidable in polynomial time (take some $EXP$-intermediate language as a prototype) and get a word problem as in the paper, it's not clear that having oracle access to $L$ will let you solve the word problem in polynomial time. In particular, how do you solve the word problem for strings that are not in the image of the function, $K$, in Theorem 1.3? $\endgroup$
    – Aubrey da Cunha
    Commented Aug 11, 2011 at 14:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .