MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Are you familiar with the Atiyah-Hirzebruch SS? – Sean Tilson Mar 27 '13 at 20:30
Yes, but only as a black-box. I do not know an algorithm to compute differentials or solve extension problems. Is this possible? – Jeremy Hahn Mar 27 '13 at 20:37
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? – Tilman Mar 27 '13 at 21:42
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. – Neil Strickland Mar 28 '13 at 7:38
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. – Sean Tilson Mar 28 '13 at 23:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.