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.