NP-complete

P 는 다항 시간 (polynomial time) 에 결정론적 (deterministically) 으로 해결 가능한 (solvable) 문제들의 집합, 주어지는 입력 (input) 이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 $X \in P$ 입니다.

NP 는 다항 시간에 비결정론적 (nondeterministically) 으로 해결 가능한 문제들의 집합으로, 어떤 결정 문제 $X$ 에 대해, 주어지는 입력이 참인지 거짓인지를 다항 시간에 비결정론적으로 해결하는 알고리즘이 존재하면 $X \in N P$ 입니다.

NP 는 P 보다 큰 집합이고 NP 는 P 보다 해결하기 어려운 문제