NP-completeness

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 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, and a brute-force search algorithm can find a valid solution 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.

Back to Complexity & Theory →

Source: Wikipedia · Image: Wikimedia Commons · Public domain