Computer Science · Theory of Computation
A topic within Theory of Computation, itself one of 13 topics in that field and part of Computer Science.
2 works
Stephen A. Cook
Proves that Boolean satisfiability is as hard as any problem whose solutions can be checked quickly, founding the theory of NP-completeness.
8 pageslink checked 17 Sept 2026Richard M. Karp
Extends Cook's theorem by proving twenty-one classic combinatorial problems, including clique, vertex cover and Hamiltonian circuit, are all NP-complete, showing intractability is the rule rather than the exception in combinatorial optimisation.