27
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ Are you familiar with the Atiyah-Hirzebruch SS? $\endgroup$
    – Sean Tilson
    Commented Mar 27, 2013 at 20:30
  • 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
    Commented Mar 27, 2013 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
    Commented Mar 28, 2013 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
    Commented Mar 28, 2013 at 23:16
  • 1
    $\begingroup$ Just thought I'd add a citation for the fact that rational homotopy groups of simply-connected spaces are NP hard here. In particular, this is not just some $\pi_1$ issue. $\endgroup$
    – Tim Campion
    Commented Aug 27, 2019 at 19:10

0

Reset to default

You must log in to answer this question.