복잡도 종류

시간·기억 공간·무작위성 같은 자원을 얼마 이하로 쓰면 풀 수 있는지에 따라 문제를 묶은 것이다(복잡도 클래스라고도 한다). P, NP, PSPACE, EXP, BPP, BQP 등이 있다. 알려진 포함 관계는 P ⊆ NP ⊆ PSPACE ⊆ EXP 이고, 이 가운데 증명된 분리는 P ≠ EXP 뿐이다. 복잡도 이론의 큰 미해결 문제는 대부분 「이 두 종류가 같은가 다른가」 꼴이며, P 대 NP 가 그 대표다.