The fundamental class of a rational space, the graph coloring problem and other classical decision problems (Q5952927)

It is possible to associate to a graph \(G\) and any integer \(k > 2\) a rational space \(S_{G,K}\) whose minimal model is generated by the vertices and edges situated in appropriate dimensions. The authors have shown earlier [Topology 39, No. 1, 89-94 (2000; Zbl 0933.55014)] that \(G\) is \(k\)-colorable iff the singular cohomology of \(S_{G,K}\) with rational coefficients is infinite dimensional. In this paper they describe an alternative view of this phenomenon. In the cohomology of \(S_{G,K}\) one can define a class, whose nonvanishing implies that the cohomology is finite. The authors give a new construction of this class, for which it is possible to produce a representative in polynomial time. The authors draw a number of conclusions on the NP-hardness of problems in the computation of rational homology classes.