P. Schupp, Generic -case Complexity and Decision Problems in Group Theory

There is a growing realization that worst-case complexity does not necessarily give a good overall picture of the difficulty of a particular problem or algorithm. The classic case is Dantzig's Simplex Algorithm for linear programming. This algorithm runs thousands of times a day in industry, always very quickly. Clever examples of Klee and Minty can make the Simplex Algorithm take exponential time, but it runs in linear time on a ``typical example''. The idea of a group-theoretic property being ``generic'' was introduced into group theory by Gromov. Genericity operates at many different levels in group theory. Kapovich, Myasnikov, Schupp and Shpilrain initiated the study of the ``generic-case complexity'' of a decision problem, for example the word problem, for a fixed finitely generated group $G$. It turns out that the word problem for many of the groups usually studied in geometric group theory has linear time generic-case complexity, usually in a very strong sense. Since generic-case complexity completely ignores the behaviour of an algorithm on a ``negligible'' set of ``difficult'' inputs, this result holds for the classic groups of Novikov and of Boone with unsolvable word problem. Generic-case results are a powerful method for proving many true average-case results where one does consider all the inputs. For example, all braid groups and all groups of prime alternating knots have average-case linear time complexity of their word problems. Furthermore, generic-case results can be proven without settling extremely difficult questions of worst-case complexity. For example, although we do not know whether or not the isomorphism problem for one-relator groups is decidable or not, the problem is generically solvable in single exponential time.
A.J. Duncan
Last modified: Wed Jun 2 18:03:16 BST 2004