NEXP (NEXPTIME, nondeterministic exponential time)
지수 길이의 증거를 지수 시간에 검증할 수 있는 문제의 모임
비결정적 튜링 기계가 지수 시간에 푸는 결정 문제의 모임으로, NP 를 지수 규모로 키운 것이다. EXP ⊆ NEXP 이고, NP ≠ NEXP 임은 증명되어 있다. 매우 큰 종류라서 「NEXP 의 문제조차 이러저러한 작은 회로로는 못 푼다」 꼴의 하한이 현재 증명 가능한 최전선에 있다. 윌리엄스의 NEXP ⊄ ACC⁰ 가 그 예다.