Linked from

The 13 pages that link to Cook–Levin theorem, each with the reason it gives.

• Computational complexity theoryBroader topic: It launched the systematic study of NP-complete problems.

• NP-completenessBroader topic: It supplies the first NP-complete problem, enabling reductions to establish hardness for others.

• P versus NP problemBroader topic: It supplies a canonical starting point for proving NP-completeness.

• Boolean satisfiability problemRelated: It establishes SAT's central status by encoding nondeterministic computation as a formula.

• Polynomial-time reductionBroader topic: It supplies the foundational starting point for many NP-completeness proofs.

• Many-one reductionBroader topic: Its reduction from nondeterministic computation launched the chain of NP-completeness proofs.

• NP-hardnessRelated: It provides the starting point for many reductions proving NP-hardness.

• Polynomial timeRelated: It established polynomial-time reductions as a way to identify the hardest problems in NP.

• Leonid LevinRelated: Levin proved an independent version establishing the same landmark result.

• Stephen CookBroader topic: Cook’s 1971 result established the first NP-complete problem.

• Clique problemRelated: Reductions from SAT help establish the hardness of clique and many related problems.

• Hartmanis–Stearns conjectureRelated: It identifies SAT as a single problem whose polynomial-time solution would settle the conjecture negatively.

• Richard M. KarpRelated: It supplied the starting point for the reduction chain behind Karp’s list.