지수 시간

단계 수가 2ⁿ, 더 넓게는 2^(n^k) 꼴로 늘어나는 계산이다. n 이 1 늘 때마다 일이 두 배가 되므로, n = 100 이면 2¹⁰⁰ ≈ 1.27 × 10³⁰ 단계가 되어 어떤 컴퓨터로도 끝낼 수 없다. 가능한 경우를 모두 해 보는 전수 조사가 전형적인 지수 시간 방법이다. P ≠ NP 를 증명하려면 NP-완전 문제에 다항 시간 알고리즘이 없음을 보이면 되고, 꼭 지수 시간이 든다는 것까지 보일 필요는 없다(그것은 더 강한 추측이다).