EXP

2^(n^k) 단계 안에 풀 수 있는 결정 문제의 모임이다. P ⊆ NP ⊆ PSPACE ⊆ EXP 이고, 시간 위계 정리에 따라 P ≠ EXP 임이 증명되어 있다. 따라서 이 사슬의 세 포함 관계 가운데 적어도 하나는 진짜로 더 큰 것이지만, 어느 것인지는 하나도 증명되지 않았다. 일반화한 체스·바둑의 필승 판정 가운데 EXP 에서 가장 어려운 것으로 증명된 문제들이 있다.