NP
← Back to Complexity Classes
The class of decision problems for which a proposed solution can be verified in polynomial time by a deterministic Turing machine. Equivalently, problems solvable in polynomial time by a nondeterministic Turing machine.
Key Properties
Related
- P (subset of NP)
- NP-Complete (hardest problems in NP)
- P vs NP Problem (open question)