Nondeterministic polynomial time (NP)
Computer Science Fundamentals
noun phrase
Definition: A complexity class of decision problems for which a proposed solution can be verified in polynomial time; equivalently, NP comprises problems solvable in polynomial time by a nondeterministic Turing machine [Xu 2025].
Example in context: “Many optimization problems belong to the NP (Nondeterministic Polynomial time) complexity class, which includes decision problems that, although not solvable in polynomial time, can be verified in polynomial time using classical strategies.” [Volpe et al. 2025]
Synonyms: NP; NP class
Related terms: decision problem; polynomial-time verifier; nondeterministic Turing machine; P; NP-complete; NP-hard