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 Classification
Statement FormCharacterization Theorem 1 Cook-Levin Theorem
Filter Results2 entries
Connections
Has Statement Form
In Branch
Principal Result Of
Source Cook-Levin Theorem (Wikipedia)
Source Cook-Levin Theorem (Wikipedia)
Proved By
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.
In Group: Computability and Complexity Theory, Lead section
In computational complexity theory, the Cook-Levin theorem, also known as
View the Source Cook-Levin Theorem (Wikipedia)
Principal Result Of: Stephen Cook, Lead sentence of the article on the result
The theorem is named after Stephen Cook and Leonid Levin.
Principal Result Of: Leonid Levin, Lead sentence of the article on the result
The theorem is named after Stephen Cook and Leonid Levin.
View the SourceReader 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.