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