NP

답이 「예」인 입력마다 짧은(다항 길이의) 증거가 있고, 그 증거가 맞는지를 다항 시간에 확인할 수 있는 결정 문제의 모임이다. 스도쿠가 풀리는지는 완성된 판을 받으면 금방 확인할 수 있다는 것이 그 예다. NP 는 「비결정적 다항 시간(nondeterministic polynomial time)」의 줄임말이지 「다항 시간이 아님(non-polynomial)」이 아니다. P 의 문제는 모두 NP 에 속한다. NP 의 문제가 모두 P 에도 속하는지, 곧 검증이 쉬우면 풀기도 쉬운지가 P 대 NP 문제다.