Karp's 21 NP-complete problems

<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, Karp's 21 NP-complete problems are a set of <a href="/facts/Computational_problem/jQ7bYUVh">computational problems</a> which are <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. In his 1972 paper, "Reducibility Among Combinatorial Problems", <a href="/facts/Richard_Karp/XtYCL0nA">Richard Karp</a> used <a href="/facts/Stephen_Cook/GdE35Sm1">Stephen Cook</a>'s 1971 theorem that the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">boolean satisfiability problem</a> is NP-complete (also called the <a href="/facts/Cook-Levin_theorem/6WN3aUyL">Cook-Levin theorem</a>) to show that there is a <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> <a href="/facts/Many-one_reduction/YUKNlYPh">many-one reduction</a> from the boolean satisfiability problem to each of 21 <a href="/facts/Combinatorics/k14xUoKT">combinatorial</a> and <a href="/facts/Graph_theory/VVPCd4TX">graph theoretical</a> computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout <a href="/facts/Computer_science/lN3pEyPz">computer science</a> are <a href="/facts/Computationally_intractable/etHuVF3U">computationally intractable</a>, and it drove interest in the study of NP-completeness and the <a href="/facts/P_versus_NP_problem/xoC7Ruda">P versus NP problem</a>.
</p>

Karp's 21 NP-complete problems open-in-new

Karp's 21 NP-complete problems