The Boolean satisfiability problem is NP-complete, meaning every problem in NP can be reduced to it in polynomial time. Proved independently by Stephen Cook and Leonid Levin, it founded the theory of NP-completeness that organizes computational complexity theory.
Facts
StatementThe Cook-Levin theorem shows that the Boolean satisfiability problem (SAT) is NP-complete: it belongs to NP, and every problem in NP can be reduced to it in polynomial time by a deterministic Turing machine. 1 Connections
Sources
1. Cook-Levin Theorem (Wikipedia)
Wikimedia FoundationIntroduction
In computational complexity theory, the Cook-Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.
Contributions
In 1971, Stephen Cook published his paper "The complexity of theorem proving procedures" in conference proceedings of the newly founded ACM Symposium on Theory of Computing.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.