From: Greg Kuperberg <greg@math.ucdavis.edu>
Subject: Re: Simpson on htpy gps
Date: Sun, 31 Jan 1999 20:32:16 +73600 (PST)

> it does seem that Anick's result (as recounted by Ravenel) is relevant,
> and apparently gives a lower bound on the computational complexity.
> Thus, for an arbitrary complex this raises the question of whether any
> known algorithm attains (in order of growth, say) the same computational
> complexity as Anick's lower bound.

To answer my own question, here is a citation for Anick's paper:

D. J. Anick, On the computational complexity of rational homotopy,
in {\it Homotopy theory (Durham, 1985)}, 1--5, Cambridge Univ. Press,
Cambridge, 1987; MR 89d:55028

According to the Math Review, he shows that computation of pi_n(X)
for a CW complex X with trivial 1-skeleton is #P-hard.  For the
benefit of people here, I can explain what #P-hard means ---
it is a convincing but very qualitative lower bound on the
difficulty of computing homotopy groups rather than a quantitative
one.

A non-deterministic computer program is one which has some blank
conditionals, like this:

if(this space intentionally left blank)
{
   one thing
}
else
{
   another
}

There is a popular understanding of non-deterministic computation as
meaning forking, meaning that the program executes both alternatives.
But what computer scientists actually have in mind is the literal
meaning of nondeterministic:  the execution of the program is not fully
determined, hence its timeline is a tree rather than a line segment.
This is analogous to, say, a fairy tale that has more than one ending.
The program is said to take polynomial time if there is a polynomial bound
on the length of longest branch of the tree, that is some polynomial in
the length of the input.

A function f from the natural numbers N to itself is said to be in #P
if for some non-deterministic program A that outputs either 0 or 1,
f(x) is the total of the values of all of the leaves of the computation
tree of A(x) (A with input x).  f is also called a counting function.
#P is similar to but less familiar than the computation class NP.
A 0-1-valued function f is in NP if for some program A, f(x) = 1 if and
only if at least one leaf of A(x) is 1.

A function F is #P-hard if any #P-function f can be expressed as f(x)
= F(g(x)), where g is a function that can be computed in deterministic
polynomial time.  Some functions are known to be #P-complete, meaning
that they are in #P and they are #P-hard.  For example the permanent
of an integer matrix is a #P-complete quantity.

So Anick's result, that homotopy groups are #P-hard, says that if you
could compute them in polynomial time, you could compute lots of things
in polynomial time.  For example you could in polynomial time determine
the number of proofs of length n^3 of a formal mathematical statement
of length n, because that is a #P function.

On the other hand, if f is #P-complete, it does not say whether it might
take time 2^n to compute f(x) with |x| = n, or time 1.00001^sqrt(n),
or maybe time 100^(n^5).  All of these are consistent with the plausible
conjecture that some #P-complete problems take exponential time.  In fact
no one knows whether #P is any larger than P, plain-old polynomial time.

It would be interesting to know whether computation of homotopy groups
is in #P.  This would amount to an "upper bound that meets Anick's
lower bound".  However, it would require a strange kind of algorithm for
computing the rank of pi_n(X) (for instance) that people have probably
not considered before.  Namely, the rank would have to be established
as a counting function for some non-deterministic computation.

Note that it was recently established by Hass, Lagarias, and Pippenger
(math.GT/9807016) that determining whether a knot projection represents
the unknot is in NP.  It is not known whether it is NP-hard.

                        Greg