Theorem

Cook-Levin Theorem

Logic and Foundations

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

Statement

The 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

Proof Year

1971 1

Classification

Statement Form

Characterization Theorem 1

Connections

Sources

1. Cook-Levin Theorem (Wikipedia)

Wikimedia Foundation

Introduction
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

Switch Atlas

The Inner World

The Civil World

The Natural World

Cook-Levin Theorem

Has Statement Form

In Branch

Proved By