Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Cook–Levin theorem
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the Cook–Levin theorem, also known as Cook's theorem, states that the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a> is <a href="/facts/NP-completeness/NFPv56DU">NP-complete</a>. That is, it is in <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>, and any problem in NP can be <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduced</a> in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by a <a href="/facts/Deterministic_Turing_machine/ojCtglYu">deterministic Turing machine</a> to the Boolean satisfiability problem. </p><p>The theorem is named after <a href="/facts/Stephen_Cook/GdE35Sm1">Stephen Cook</a> and <a href="/facts/Leonid_Levin/1CeP1EJB">Leonid Levin</a>. The proof is due to <a href="/facts/Richard_Karp/XtYCL0nA">Richard Karp</a>, based on an earlier proof (using a different notion of reducibility) by Cook. </p><p>An important consequence of this theorem is that if there exists a deterministic polynomial-time algorithm for solving Boolean satisfiability, then every <a href="/facts/NP_(complexity)/6muUfVMI">NP</a> problem can be solved by a deterministic polynomial-time algorithm. The question of whether such an algorithm for Boolean satisfiability exists is thus equivalent to the <a href="/facts/P_versus_NP_problem/xoC7Ruda">P versus NP problem</a>, which is still widely considered the most important unsolved problem in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>. </p>