15
$\begingroup$

If G is a finitely presented group (with generating set X) and w is a word over X such that w=1 in G, then the latter can be witnessed by a so called van Kampen diagram for w, which is a planar diagram where for each region the boundary cycle is labelled with a group relator, and the boundary of the whole diagram is labelled with the word w.

Is there a finitely presented group G (with generating set X) such that the following hold?

  • G has polynomial Dehn function
  • G has a polynomial time word problem
  • There is no polynomial time algorithm for the following problem:

    INPUT: A word w over X such that w=1 in G

    OUTPUT: A van Kampen diagram for w

In other words: We can efficiently check whether w=1 in G but we cannot compute efficiently a witness for this fact (but we know that a small witness exists).

If the answer to the above question is positive, one certainly needs some complexity theoretic assumption. A reasonable starting point might be to assume that a nondeterministic polynomial time Turing machine M exists such that:

  • One can check in deterministic polynomial time whether an input w is accepted by M.
  • There is no polynomial time Turing machine that computes for a given word w (that is
    accepted by M) an accepting computation of M for input w.
$\endgroup$
9
  • 2
    $\begingroup$ The assumption in the last paragraph is simply $\mathrm P\ne\mathrm{NP}$, or am I missing something? $\endgroup$ Oct 31, 2013 at 15:51
  • $\begingroup$ Since you can move from a van Kampen diagram using one presentation to another in polynomial time, I think this question is independent of $X$, so you are just looking for a suitable group. Since verifying the correctness of a candidate diagram can be done in polynomial time, perhaps the best you can hope for is to find an example in which you could prove the problem was NP-complete. But I've no idea how to look for suitable candidates! $\endgroup$
    – Derek Holt
    Oct 31, 2013 at 19:06
  • $\begingroup$ Yes, since any group with polynomial Dehn function has word problem in NP (and the certificate is more or less a van Kampen diagram), it seems like an answer to the question would imply $P\neq NP$. Could you clarify the connection? $\endgroup$
    – HJRW
    Nov 2, 2013 at 12:13
  • 1
    $\begingroup$ @Emil: I am not sure, whether the assumption implies that P and NP are different. I thought its more a condition similar $\endgroup$ Nov 5, 2013 at 15:08
  • 2
    $\begingroup$ Ah, now I noticed what I was missing, namely the requirement that the machine, although nondeterministic, actually computes a language in P. Sorry. You can assume without loss of generality that your $M$ accepts every input. Then it should be clear that the existence of such a machine is equivalent to the existence of a total NP-search problem that cannot be solved in polynomial time (i.e., FP ≠ TFNP). This is a stronger assumption than P ≠ NP, but it is implied by P ≠ NP ∩ coNP, or for that matter, by the existence of one-way permutations. $\endgroup$ Nov 6, 2013 at 12:41

1 Answer 1

6
$\begingroup$

This is equivalent to $P\ne NP$ by the result of the paper : Birget, J.-C.; Olʹshanskii, A. Yu.; Rips, E.; Sapir, M. V. Isoperimetric functions of groups and computational complexity of the word problem. Ann. of Math. (2) 156 (2002), no. 2, 467–518.

Update See the discussion here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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