11
$\begingroup$

Computation of stable homotopy groups (for example of sphere) is hard, but still, not as hard as unstable ones.

For unstable homotopy groups there are some results showing that there cannot be efficient algorithms for computing homotopy group of finite CW complexes, for example . D.Anick's paper The Computation of Rational Homotopy Groups is #P-Hard show that even just computing the rational part is already #P-hard, so there is essentially no hope of having polynomial time algorithm to do it (I don't know my complexity classes very well, but I'm willing to assume that $P \neq NP$ if necessary to make that last claim correct).

But D.Anick's paper is very 'unstable' in his approach: in the stable workd rational homotopy groups are justs homology groups, so they are are easy to compute algorithmically, and moreover his proof relies heavily on the connection with the homology groups of the loop spaces of a finite CW-complexes, which is a very unstable thing to look at (stably, those are justs the ordinary homology groups).

(There is apparently also a more recent paper with more precise obstruction for the unstable case, but I havn't look at it in much detail yet.)

So my question: is there any proof that there are no polynomial time algorithms which compute stable homotopy groups of finite CW-complexes (or justs of sphere, which as far as I know is pretty much the same) ?

Of course such an algorithm is expected to not exists, but I don't know if this is a "conjecture" or a known fact.

This question is just by pure curiosity, but I couldn't find anything discussing it and it sounded like it might be of interest.

$\endgroup$
  • $\begingroup$ The following paper does not directly address your question but it might be relevant: "The computation of the Betti numbers of an elliptic space is a NP-hard problem" by Antonio Garvin and Luis Lechuga, Topology and its Applications 131 (2003), 235-238. Note, by the way, that hardness results in complexity theory don't automatically imply that the problems are hard to solve in practice. There are plenty of NP-hard and even #P-hard problems out there that are routinely solved (or approximately solved) in practice. $\endgroup$ – Timothy Chow Sep 18 '18 at 16:46
  • $\begingroup$ If you haven't already done so, you might also try asking Francis Sergeraert. www-fourier.ujf-grenoble.fr/~sergerar $\endgroup$ – Timothy Chow Sep 18 '18 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.