NP-completeness

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, a problem is NP-complete when:

<ol><li>It is a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a>, meaning that for any input to the problem, the output is either "yes" or "no".</li>
<li>When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution.</li>
<li>The correctness of each solution can be verified quickly (namely, in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>) and a <a href="/facts/Brute-force_search/YU2fzBIt">brute-force search</a> algorithm can find a solution by trying all possible solutions.</li>
<li>The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.</li></ol>
The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to <a href="/facts/Nondeterministic_Turing_machine/zv2x6XPG">nondeterministic Turing machines</a>, a way of mathematically formalizing the idea of a brute-force search algorithm. <a href="/facts/Polynomial_time/77T62gmf">Polynomial time</a> refers to an amount of time that is considered "quick" for a <a href="/facts/Deterministic_algorithm/v8x4wz35">deterministic algorithm</a> to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "<a href="/facts/Complete_(complexity)/Ine1b8Qy">Complete</a>" refers to the property of being able to simulate everything in the same <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a>.
More precisely, each input to the problem should be associated with a set of solutions of polynomial length, the validity of each of which can be tested quickly (in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>), such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>, an abbreviation for "nondeterministic polynomial time". A problem is said to be <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> if everything in NP can be transformed in polynomial time into it even though it may not be in NP. A problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC.
Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the <a href="/facts/P_versus_NP_problem/xoC7Ruda">P versus NP problem</a>, is one of the fundamental <a href="/facts/List_of_open_problems_in_computer_science/QySnBJ5E">unsolved problems in computer science</a> today.
While a method for computing the solutions to NP-complete problems quickly remains undiscovered, <a href="/facts/Computer_scientist/DavggjGL">computer scientists</a> and <a href="/facts/Computer_programmer/WGTS1Jv9">programmers</a> still frequently encounter NP-complete problems. NP-complete problems are often addressed by using <a href="/facts/Heuristic_(computer_science)/PM2qkoa2">heuristic</a> methods and <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a>.

NP-completeness open-in-new

NP-completeness