From: Greg Kuperberg <greg@math.ucdavis.edu>
Date: Sun, 31 Jan 1999 13:23:41 -0800 (PST)
Subject: Re: Simpson on htpy gps

As Carlos Simpson points out, it's a theorem of Edgar Brown that
computing homotopy groups of a simply-connected simplicial complex
is recursive.  This type of result is what I had in mind all along,
but there are two major difficulties:

1) The computational complexity is very bad, or so I hear.  What is the
complexity of the Brown algorithm to compute pi_k(S^n)?
Is it known or knowable?  Can one give reasonable bounds?

2) The computational complexity problem is compounded by difficulties
with data structures and programming langauges.  My impression is that
with many algorithms in homological algebra, it is very tempting to
sacrifice an exponential amount of time and space in order to have
reasonably simple implementation of a particular theoretical algorithm.

I'm certainly interested in this result of Anick on the computational
complexity of computing homotopy groups of a complex with 2-cells
and 4-cells.  Can someone give a reference?

Finally Doug Ravenel made what I consider an inaccurate statement about
when a computer algorithm is useful, namely when it runs in polynomial
time.  To the contrary, a computer algorithm is interesting when the
computer can do more important cases than those that can be done by hand.
In many cases this is precisely because the problem takes exponential
time.  A substantial fraction of the research in computer algorithms
is in passing from severe exponential time to mild exponential time.
The travelling salesman problem is one example.  Another example is
factoring numbers.  Chess is a third example. By constrast computational
problems which are known to be doable in polynomial time --- like sorting
lists or multiplying matrices --- are relatively boring, even though
they are important in practice.

                        Gerg