(definition)
Definition: The complexity class of decision problems for which answers can be checked by an algorithm whose run time is polynomial in the size of the input. Note that this doesn't require or imply that an answer can be found quickly, only that any claimed solution can be verified quickly. "NP" is the class that a Nondeterministic Turing machine accepts in Polynomial time.
Also known as nondeterministic polynomial time.
Specialization (... is a kind of me.)
NP-complete.
See also P, NP-hard, RP, ZPP, BPP, big-O notation.
Note: For instance, a "yes" answer to the question, "is there a Hamiltonian cycle, or tour, of a certain graph?" can be quickly checked given a certificate for the answer. We can quickly check that the path which is the certificate, indeed, starts and ends at the same vertex, contains every other vertex exactly once, and only uses valid edges. Another example is that a purported sorting of an input can be verified in O(n log n). This can be done by sorting the input (again), then comparing it with the purported sorting.
Being in NP doesn't require that a negative answer, e.g. "there is no tour", can be quickly checked.
Author: PEB
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP. Wikipedia entry on Complexity classes P and NP.
Scott Aaronson's Complexity Zoo
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 5 January 2021.
HTML page formatted Tue Jan 5 09:25:05 2021.
Cite this as:
Paul E. Black, "NP", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 5 January 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/np.html