# Computing van Kampen diagrams

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.
• The assumption in the last paragraph is simply $\mathrm P\ne\mathrm{NP}$, or am I missing something? – Emil Jeřábek Oct 31 '13 at 15:51
• 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! – Derek Holt Oct 31 '13 at 19:06
• 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? – HJRW Nov 2 '13 at 12:13
• @Emil: I am not sure, whether the assumption implies that P and NP are different. I thought its more a condition similar – Markus Lohrey Nov 5 '13 at 15:08
• 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. – Emil Jeřábek Nov 6 '13 at 12:41

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.