NP

NP, short for nondeterministic polynomial time, is the class of decision problems for which a given answer can be verified in polynomial time if a correct certificate is provided. In formal terms, a language is in NP if there exists a nondeterministic Turing machine that decides the language in time polynomial in the input length. Equivalently, there is a deterministic polynomial-time verifier V such that, for any input x, x is in the language if and only if there exists a certificate y of length polynomial in |x| with V(x, y) accepting.

NP is related to the class P, which consists of problems solvable in deterministic polynomial time. It is known that P is a subset of NP, but whether P equals NP remains one of the central open questions in theoretical computer science.

A problem is NP-complete if it lies in NP and is at least as hard as every problem in NP, in the sense that every NP problem can be reduced to it in polynomial time. NP-complete problems are the hardest problems in NP under polynomial-time reductions. Examples include boolean satisfiability (SAT), 3-SAT, the CLIQUE problem, VERTEX COVER, and the Hamiltonian cycle problem. NP-hard problems are at least as hard as the hardest problems in NP, but they do not have to be in NP themselves; some NP-hard problems are not decision problems or are undecidable.

In practice, NP-completeness is used as a measure of problem difficulty: if a problem is NP-complete, no known polynomial-time algorithm exists (unless P = NP) and efficient exact solutions are unlikely for large instances. Many practical problems are approached with heuristics and approximation algorithms.