시간 위계 정리

하트마니스와 스턴스가 1965년에 처음 증명한, 계산 복잡도 이론의 출발점이 된 정리다. 오늘날 알려진 꼴로는, 시간 한도 g(n) 이 f(n)·log f(n) 보다 본질적으로 빨리 자라면 g(n) 시간에는 풀리지만 f(n) 시간에는 풀리지 않는 문제가 있다. 이로부터 P ≠ EXP 가 나온다. 증명은 대각선 논법이다. 같은 종류의 자원(시간과 시간)을 견줄 때는 강력하지만, 결정적 시간과 비결정적 시간처럼 종류가 다른 자원을 견주는 P 대 NP 에는 그대로 쓸 수 없다.