Concise definitions for algorithms, complexity, and systems concepts. Each term has its own indexable page — browse below or search.
3 terms
-
NP
(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.… Read full definition →
-
NP-Complete
NP complete problems are the hardest problems in NP: they are in NP, and every problem in NP reduces to them in polynomial time. If any NP complete… Read full definition →
-
NP-Hard
NP hard problems are at least as hard as every problem in NP. A polynomial time algorithm for any NP hard problem would yield a polynomial time algorithm… Read full definition →