Distributional Word Problem for Groups
Jie Wang · SIAM Journal on Computing · 1999
This paper studies the word problem for finitely presented groups under the restriction that words can only be rewritten for a bounded number of times. We obtain a similar result to the Novikov--Boone theorem in the setting of average-case NP-completeness. The word problem we consider here is to decide, when given a finite presentation of a group G, words x, y, z, and an integer k, whether (x -1 yx )z can be derived from z(x -1 yx )z in the presentation of G in k steps. We show that when each component of the instance is chosen uniformly at random, the problem cannot be solved fast on average unless every NP problem under every reasonable distribution on instances can be solved fast on average.