Complexity Explorer Santa Few Institute

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.