Homotopy Groups – Computational Complexity of Computing Homotopy Groups of Spheres

at.algebraic-topologycomputational complexity

At various times I've heard the statement that computing the group structure of $\pi_k S^n$ is algorithmic. But I've never come across a reference claiming this.

Is there a precise algorithm written down anywhere in the literature? Is there one in folklore, and if so what are the run-time estimates? Presumably they're pretty bad since nobody seems to ever mention them.

Are there any families for which there are better algorithms, say for the stable homotopy groups of spheres? or $\pi_k S^2$ ?

edit: I asked Francis Sergeraert a few questions related to his project. Apparently it's still an open question as to whether or not there is an exponential run-time algorithm to compute $\pi_k S^2$.

Best Answer

Francis Sergeraert and his coworkers have implemented his effective algebraic topology theory in a program named Kenzo. It seems capable of computing any $\pi_n(S^k)$ (in fact homotopy groups of any simply connected finite CW complex), although I don't know how far it is feasible. For instance $\pi_6 S^3$ is computed in about 30 seconds. In a 2002 paper, they mention other algorithms by Rolf Schön and by Justin Smith, not implemented at that time.

Related Solutions

[Math] Why is “P vs. NP” necessarily relevant

The $P \ne NP$ problem is the best way we know to formulate the belief (which was expressed even before the problem was formally stated) that certain specific algorithmic problems (such as finding a Hamiltonian cycle in a graph) requires exponential number of steps as a function of their description. The formulation is based on the important notion of a nondeterministic algorithm. The conjecture that P is not equal to NP is the basis of a mathematical theory of complexity which is remarkably beautiful. It is likely that a proof for the conjecture will lead to better understanding of the limitations of computation which will go beyond the conjecture itself. (Unfortunately we are very far from such a proof.) A counterexample (which is not expected) may lead to a major change of our reality and not just our understanding of it. (I suppose this is one of the main reasons in believing the conjecture.) Your concern is that maybe, because of the asymptotic nature of the conjecture, we can question its real relevance. Namely problems we regard as intractable may still be even if P=NP because of huge constants in the polynomial involved, or perhaps even if NP not equal P there can be efficient algorithm to relevant cases of intractable problems. These are serious concerns that are often raised and sometimes there are efforts to study them scientifically.

Overall, it looks that these asymptotic concerns are secondary compared to the problem itself. Moreover, there are many examples that the asymptotic behavior and practical behavior are similar beyond what the theory dictates (but a few examples also in the other direction). There are other related concerns regarding the relevance for the $P \ne NP$ problem. Is the worst case analysis relevant to practical problems? Is the hardness apply when we are interested in approximate solution rather than in exact solution? Both these questions (like the asymptotic issue) can be regarded as secondary in importance compared to the $NP \ne P$ problem itself but otherwise very important. Indeed both hardness of approximation and average case analysis are very central research topics.

(A side remark, there is something unnatural about the way Graham's numbers are used in the question. You are dealing with a decision problem where the answer is always yes when n is sufficiently large. And there is a simple polynomial time algorithm as a function of n to decide the answer for a every given n. So the relevance of this particular example (which is interesting) to the question asked about NP complete problems (which is also interesting) is not so strong.)

Finally, regarding relevance. Andreas raised the interesting possibility that NP=P but the constant involved are so huge that the polynomial algorithm for solving NP complete problems is utterly not practical. A related interesting possibility is that there even exists a practical polynomial time algorithm for NP complete problems but that finding this algorithm itself is computationally intractable. As I said, both these possibilities are considered unplausible. Even if true they will not harm the relevance of the NP=P problem in making the central distinction between intractable and tractable problems. In order to make these concerns interesting one should come up with a theoretical framework to study them, and then study them fruitfully. (As I mentioned above, this was done for related concerns regarding approximation and regarding average case behavior.)

[Math] Under what conditions does an Integer Programming problem run in polynomial time

The way I think about Kannan's algorithm (or, for that matter, any of the several "Lenstra-type" algorithms which present similar bounds as the original Lenstra algo from 1983) is that it's designed with the extreme worst-case instances of integer programming (IP) in mind. The goal here is to get a small (i.e., polynomial) bound on the complexity of the general problem instance without any assumptions about any special structure of the input (matrix $A$, or even $B$).

Notice that IP with totally unimodular (TU) $A$ matrix is solvable in polynomial time not by Kannan's algorithm (or by any of the Lenstra-type algorithms), but by simply solving the IP as a linear program, which could be done in polynomial time, and we get integrality "for free" in that process. Other generalizations of TU matrices such as balanced matrices or total dual integrality (TDI) also guarantee integrality "for free" in a similar fashion as instances where $A$ is TU (some times with additional assumptions on $B$ also). Recently (STOC '17), Artmann, Weismantel, and Zenklusen gave a strongly polynomial algo for bimodular IPs, where $|\det(S)| \leq 2$ for all submatrices $S$ of $A$ (preprint might be available on ResearchGate). People have also considered the natural generalization of this problem where $|\det(S)| \leq \Delta$ for higher (but fixed) values of $\Delta$. The latest preprint by Gribanov provides an FTP algo for instances of IP where $A$ is "near square" (see the preprint for details). But again, all these families of algorithms somehow use the special problem structure, e.g., $|\det(S)| \leq \Delta$ (on a related note, we have studied (arXiv) a class of IP instances where $A$ is not TU, no fixed bound on $|\det(S)|$ is assumed, but still the LP relaxation of the IPs are guaranteed to have integer optimal solutions; but even here, the problems have a different kind of special structure).

In other words, the Lenstra-type algos (including Kannan's) are not designed to work better (or faster) on any specific subclass of IPs with special structure. As such, it's not surprising no such obvious instances have been identified as yet.

Best Answer

Related Solutions

[Math] Why is “P vs. NP” necessarily relevant

[Math] Under what conditions does an Integer Programming problem run in polynomial time

Related Question