8

Is the best known worst-case running time for calculating the homotopy groups of spheres $\pi_n(S^k)$ bounded by a finite tower of exponentials? How high is a tower? Does $O(2^{2^{2^{2^{n+k}}}})$ suffice?

What is the best known asymptotic upper bound for the order of the torsion part of this group?

I am aware of the discussion here Computational complexity of computing homotopy groups of spheres, but it does not even say whether the worst case is bounded by a finite stack of exponentials, let alone give an upper bound for the height of the stack.

Tim Campion
  • 60,951
Joe Shipman
  • 819
  • 4
    This paper seems to say that, at least for odd-dimensional spheres, it can be done in double-exponential time: https://math.mit.edu/research/undergraduate/urop-plus/documents/2021/Allen.pdf – Kevin Casto Feb 13 '23 at 16:10
  • Are you particularly interested in unstable homotopy groups of spheres, or will the stable range suffice? I would suspect increased efficiency is possible in the latter case. Then again, I might also suspect the speedup is not actually known. – Tim Campion Feb 14 '23 at 17:39
  • Note also that for $n$ fixed, the complexity is at most polynomial in $k$. This was mentioned by Charles Rezk on the other question. (Thm 1.3 that Kevin Casto mentions fixes $k$ and is (better than) double exponential in $n$) – Tim Campion Feb 14 '23 at 18:05
  • I am interested in all of them, which is two dimensions of variation, rather than the single dimension of variation given by the stable ones. By the way, the subtext is “has any progress been made since the 50’s and 60’s on improving worst-case complexity, it’s weird that it doesn’t seem to have been”, and the paper is not a faster algorithm but a sharper analysis of the original algorithm so my impression remains unchanged (but it’s an excellent and commendable paper! It partially answers the original question I wanted to do my thesis on, before I switched from complexity theory to logic). – Joe Shipman Feb 14 '23 at 21:50

0 Answers0