Problems that cannot necessarily be solved in polynomial time on a sequential computer but can be solved in polynomial time on a nondeterministic computer which, roughly speaking, guesses in turn each of 2N possible values of some N-bit quantity.