NP-complete

thumb|upright=0.8|It can be difficult to find a valid solution to a Sudoku puzzle, but once a solution has been found its validity can be verified easily. It is NP-complete to determine whether an Sudoku has a valid solution.

In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. Somewhat more precisely, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". Each input to the problem is associated with a collection of short (polynomial length) solutions, which might or might not validly solve the input. The output is "yes" when at least one of these solutions is valid, and "no" when none of them are. The validity of each solution can be verified quickly (namely, in polynomial time), and a brute-force search algorithm can find a valid solution (if one exists) by trying all possible solutions. The problem can be used to simulate every other problem for which we can verify quickly that a solution is valid. Hence, if we could find valid solutions of some NP-complete problem quickly (when they exist), we could quickly find valid solutions for every other problem in which a given solution can be easily verified. Problems that meet the first three criteria belong to the class NP, which is short for "nondeterministic polynomial-time". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. A problem that is in NP and also meets the fourth criterion is said to be "NP-complete". The term "complete" refers to the property of being able to simulate everything in the same complexity class: If some NP-complete problem has a polynomial time algorithm, all problems in NP do.