Revision #868 → #1432 · back to history
addedNP-complete problem (informal)a5481ac3e247
addedClass NP1375cd49aa7f
addedNP-complete (formal)d494d5c0e162
addedCook–Levin theoremc67b864945e0
addedKarp's 21 NP-complete problemsa733d740507e
addedList of NP-complete problems2e4a946faacd
added3-SAT vs 2-SAT vs Max-2-SAT4ce5647b2ac5
addedGraph coloring boundaryb201854e27e4
addedCycle/bipartite vs maximum subgraphfed0ae6bbc67
addedKnapsack approximation vs exact776ce9670621
addedGraph isomorphism as NP-intermediatef392030a83f4
addedExistence of NP-intermediate problemsad8776adee92
addedSuperpolynomial time for known NP-complete algorithmsc83256ffb7ec
addedPolynomial-time Turing reductionc617a4b0cfc4
addedLogarithmic-space many-one reduction66fa19bc3d68
addedLog-space implies polynomial-time reduction80d57f1688c8
addedAC0 reductions strictly weakerdf4ccc04c5b0
addedPresburger arithmetic requires more than exponential timea572a946fd92
addedHalting problem unsolvable574c1643ff63
addedValiant–Vazirani theorem2502638bc7b1
addedSubexponential algorithms via planar separatorb819cae73e18
addedPolynomial-time algorithms must err often unless P=NP877474485bb5
addedBQP and NP-completeness8b15829e24c0
addedNon-closure of NPC25783d33649c
addedNPC closure under complement equivalent to NP=co-NP4934f23850bf