Complexity Explorer Santa Fe Institute


NP

Refers to the class of nondeterministic polynomial time problems:  those for which there is no known polynomial-time algorithm to solve the worst-case instances, but for which there is a polynomial-time algorithm to verify whether a candidate solution to a problem instance is indeed a solution.   See also P.


Topics
Computer Science, Computation, Mathematics
Difficulty
1