Revision #98 → #1123 · back to history
addedCook–Levin theorem (SAT is NP-complete)b97f14c6d9f1
addedPolynomial SAT algorithm implies P = NP6ac9693f3b25
addedBaker–Gill–Solovay oracle separationcf820992f899
addedLevin's optimal-time algorithms67f0827a70eb
addedDecision problem in NP21e6472d72dd
addedInstance of Boolean satisfiability problem99b7955ed935
addedSatisfiable expression89585d2129a3
addedSAT is in NPc14572b004ee
addedEvery NP problem reduces to SAT23b6adaf03ce
addedConstruction of Boolean expression satisfiable iff machine acceptsf8f664c2bfa4
addedTransformation is a polynomial-time reductionc3cab0fc1fab
addedQBF is PSPACE-complete840e71418431
addedDQBF is NL-completeb6d51ac00ac3
addedNP reduces to SAT in logarithmic space6d3a158cec00
addedKarp's 21 NP-complete problems3886acbd83af
added3SAT is NP-complete872a2d5a9f69