I am a novice with K-theory trying to understand what is and what is not possible.

Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with field coefficients. However, it is known that computing the rational homotopy groups of $X$ is at least $NP$-hard (in fact, at least $\# P$-hard), simply because it is possible to reduce NP-hard problems to the computations of some rational homotopy groups.

For any of: (1) Real K-theory, (2) Complex K-theory, (3) p-adically completed K-theory, is there an algorithm to compute $K^0$ of a finite simplicial complex? Is this algorithm polynomial-time?

If there is no known algorithm, is there at least evidence that any theoretical algorithm, should it exist, must be at least $NP$-hard? In other words, is there any way to reduce an $NP$-hard problem to the calculation of some $K$ group?

  • $\begingroup$ Are you familiar with the Atiyah-Hirzebruch SS? $\endgroup$ – Sean Tilson Mar 27 '13 at 20:30
  • $\begingroup$ Yes, but only as a black-box. I do not know an algorithm to compute differentials or solve extension problems. Is this possible? $\endgroup$ – Jeremy Hahn Mar 27 '13 at 20:37
  • 6
    $\begingroup$ Probably not. The first differential is easy (for KU), it's determined by a cohomology operation, but I think the higher ones are algorithmically intractable and would describe higher-order cohomology operations. Maybe one should try to describe vector bundles on finite simplicial complexes combinatorially instead? $\endgroup$ – Tilman Mar 27 '13 at 21:42
  • 8
    $\begingroup$ I have thought about this occasionally. There is some reason to think that there might be a tractable combinatorial construction of a minimal Kan complex of homotopy type $\Omega^\infty(KU/2)$. From that it should be possible to determine the computational complexity of $(KU/2)^*(X)$. Odd primes might be possible as well. I have various kinds of calculations related to this, but no real conclusion. $\endgroup$ – Neil Strickland Mar 28 '13 at 7:38
  • 1
    $\begingroup$ Dominique Arlettaz has a result regarding the order of differentials in the Atiyah-Hirzebruch spectral sequence, see "The order of the differentials in the Atiyah-Hirzebruch spectral sequence". I would imagine that one might be able to make certain conclusions if you assumed enough about the torsion of the homology of the space. However, on rereading your question I realize this is not so much what you were interested in. Thought I'd mention the paper of Arlettaz just in case though. $\endgroup$ – Sean Tilson Mar 28 '13 at 23:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.