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.
Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ The assumption in the last paragraph is simply $\mathrm P\ne\mathrm{NP}$, or am I missing something? $\endgroup$
    – Emil Jeřábek
    Commented 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
    Commented 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
    Commented 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$
    – Markus Lohrey
    Commented 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$
    – Emil Jeřábek
    Commented Nov 6, 2013 at 12:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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