NP

Also known as: Nondeterministic Polynomial Time

NP (nondeterministic polynomial time) is the class of decision problems whose yes-instances have a certificate that can be checked in polynomial time.

Membership in NP is about verification, not about finding the answer. Sudoku is a standard example: a filled grid is easy to check, even if finding one is hard.

← Back to CS Glossary