KnowraCook–Levin theoremLinked fromLinked fromThe 13 pages that link to Cook–Levin theorem, each with the reason it gives.All 13Broader topic 6Related 7Boolean satisfiability problemRelated: It establishes SAT's central status by encoding nondeterministic computation as a formula.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.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.