HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 2. P vs NP의 현재까지의 증명 노력들
  3. 2-4 알려진 부분 결과

시간 위계 정리 — 시간을 더 주면 더 풀 수 있다

Hartmanis 와 Stearns 의 시간 위계 정리는 시간을 충분히 더 주면 풀 수 있는 문제가 반드시 늘어난다는 것을 대각선 논법으로 증명한다. P ≠ EXP 가 여기서 나온다. 그러나 같은 방법으로 P 와 NP 사이는 가르지 못한다.

  • 중급
  • 관리자
  • 조회 0
  • AI 도움
검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.

시간 위계 정리는 시간을 충분히 더 주면 풀 수 있는 문제가 반드시 늘어난다는 정리다. 이 글은 그 정확한 진술과 대각선 논법으로 된 증명의 얼개를 보고, 같은 방법으로는 왜 P 와 NP 사이를 가르지 못하는지 짚는다.

정확한 진술

DTIME(f(n)) 은 결정적 튜링 기계가 길이 n 인 입력을 f(n) 의 상수 배 걸음 안에 판정하는 언어의 클래스다.

시간 위계 정리(time hierarchy theorem, 「시간 계층 정리」라고도 옮긴다)는 다음을 말한다.

시간 위계 정리 증명됨

f 와 g 가 시간 구성 가능한 함수이고 f(n)·log f(n) = o(g(n)) 이면, DTIME(f(n)) ⊊ DTIME(g(n)) 이다.

시간 구성 가능(time-constructible)이란 n 이 주어졌을 때 f(n) 이라는 값 자체를 f(n) 의 상수 배 시간 안에 계산해 낼 수 있다는 뜻이다. n log n, n², 2ⁿ 같은 흔한 함수는 모두 그렇다. o(·) 는 두 함수의 비가 0 으로 간다는 표기다.

이 정리는 Hartmanis 와 Stearns 의 1965년 논문에서 비롯되었다. 원 논문의 정리 9 는 조건이 더 세서, T(n)²/U(n) 의 하극한이 0 이면 시간 U 로는 계산되지만 시간 T 로는 계산되지 않는 수열이 있다는 꼴이었다(T 와 U 는 실시간으로 셀 수 있는 증가 함수). 제곱은 테이프가 여러 개인 기계들을 테이프 수가 고정된 기계 하나로 흉내 내는 비용이다. 이듬해 Hennie 와 Stearns 가 흉내 내는 비용을 로그 배로 낮추면서 지금의 log f(n) 꼴이 되었다.

뜻

  • n² 시간이면 풀리지만 n 시간으로는 풀리지 않는 문제가 있다. n^100 과 n^99 사이에도 있다.
  • P ⊊ EXP 다. P ⊆ DTIME(2ⁿ) ⊊ DTIME(2^(2n)) ⊆ EXP 이기 때문이다. 다항 시간으로는 절대 풀 수 없는 문제가 지수 시간 안에 실제로 있다.
  • 비결정적 기계에도 같은 정리가 있다. f(n+1) = o(g(n)) 이면 NTIME(f(n)) ⊊ NTIME(g(n)) 이다. Cook 이 1972년에 처음 증명했고, 지금 교과서에 실리는 간단한 증명은 Žák 의 1983년 논문에서 왔다. 여기서 NP ⊊ NEXP 가 나온다.
  • 기억 공간에 대해서도 같은 꼴의 위계 정리가 성립한다.

곧 복잡도 클래스들은 한 덩어리로 뭉개지지 않고 끝없이 이어지는 사다리를 이룬다.

겹겹이 포개진 상자 그림. 안쪽부터 DTIME(n), DTIME(n²), P, DTIME(2ⁿ), DTIME(2^(2n)), EXP 순서로 바깥 상자가 안쪽 상자를 품는다. DTIME(n) 과 DTIME(n²) 사이의 띠에 점이 찍혀 있고 n² 시간이면 풀리지만 n 시간으로는 풀리지 않는 문제가 있다고 적혀 있다. DTIME(2ⁿ) 과 DTIME(2^(2n)) 사이의 띠에도 점이 찍혀 있고, 다항 시간으로는 절대 풀 수 없는 문제가 지수 시간 안에 실제로 있으므로 P ⊊ EXP 라고 적혀 있다.
시간을 더 주면 풀리는 문제의 모임이 실제로 커진다. 상자 사이 띠에 찍힌 점이 위계 정리가 있다고 보장하는 문제다. 사다리의 칸 가운데 몇 개만 그렸다.

증명의 핵심 생각 — 대각선 논법

Cantor 가 실수를 다 셀 수 없음을 보일 때, Turing 이 정지 문제를 풀 수 없음을 보일 때 쓴 대각선 논법(diagonalization)을 시간 제한이 있는 계산으로 줄여 옮긴 것이다. 교과서의 본보기인 DTIME(n) ⊊ DTIME(n^1.5) 로 얼개를 보자.

  1. 기계 D 를 만든다. D 는 입력 x 를 어떤 기계 Mₓ 의 설명서로 읽는다. 그리고 만능 튜링 기계로 Mₓ 를 바로 그 입력 x 위에서 |x|^1.4 걸음 동안 흉내 낸다. 그 안에 Mₓ 가 답을 내면 D 는 반대로 답하고, 못 내면 0 을 답한다.
  2. D 는 n^1.5 시간 안에 끝난다. 그러므로 D 가 판정하는 언어 L 은 DTIME(n^1.5) 에 속한다.
  3. L 을 선형 시간에 판정하는 기계 M 이 있다고 해 보자. 만능 기계가 M 의 T 걸음을 흉내 내는 데는 T log T 의 상수 배면 충분하다. 어떤 기계든 무한히 많은 문자열이 그것을 나타내므로, M 을 나타내는 충분히 긴 x 를 고를 수 있다. 그 x 에서 D 는 제한 시간 안에 M(x) 를 알아내고 뒤집는다. D(x) ≠ M(x) 이니 M 은 L 을 판정하지 못한다. 모순이다.

정리에 log f(n) 이 붙는 까닭이 3번에 있다. 그것이 만능 기계가 남을 흉내 낼 때 치르는 값이다.

대각선 논법을 표로 그린 그림. 줄은 입력 x 가 나타내는 기계 M₁ 부터 M₅, 칸은 입력 x₁ 부터 x₅ 이고, 각 칸에 그 기계가 그 입력에 낸 답 0 또는 1 이 적혀 있다. 대각선 칸이 강조되어 있고, 셋째 대각선 칸은 제한 걸음 안에 답을 내지 못한 경우다. 맨 아래 D 의 답 줄은 대각선 칸을 뒤집은 값이고, 답을 내지 못한 칸 아래는 0 이다.
D 는 입력 x 마다 기계 Mₓ 를 바로 그 x 위에서 흉내 낸 답(대각선 칸)을 뒤집는다. 칸의 0·1 은 설명을 위해 넣은 보기 값이다.

P 대 NP 까지의 거리

위계 정리는 같은 종류의 기계에 시간만 더 준 경우를 가른다. P 와 NP 의 차이는 양이 아니라 종류다. 여기서 대각선 논법은 두 가지 벽을 만난다.

  • 뒤집으려면 흉내 낼 수 있어야 한다. Fortnow 는 대각선 논법에 흉내가 꼭 필요한데, 정해진 NP 기계 하나가 임의의 다항 시간 기계를 흉내 내는 방법을 우리가 모른다고 적는다.
  • 증명이 상대화(relativization)한다. 위 증명은 기계의 속을 들여다보지 않고 걸음을 따라갈 뿐이어서, 모든 기계에 같은 오라클(신탁)을 달아 주어도 그대로 성립한다. 그런데 Baker, Gill, Solovay 는 1975년에 P 와 NP 가 같아지는 오라클과 달라지는 오라클이 모두 있음을 보였다. 그러니 상대화하는 증명만으로는 어느 쪽 결론도 낼 수 없다.

위계 정리는 지나간 도구도 아니다. Williams 가 2011년에 발표한 NEXP ⊄ ACC⁰ 의 증명은 마지막 걸음에서 비결정적 시간 위계 정리와 모순을 일으켜 끝난다.

출처

출처·이용 조건: 직접 작성

참고문헌 9

  • 원전원문 확인
    On the computational complexity of algorithmsJuris Hartmanis, Richard E. Stearns · 1965Transactions of the American Mathematical Society 117 (1965), 285–306쪽

    계산에 드는 시간으로 문제를 분류하는 틀을 세우고 시간 위계 정리를 증명한 논문이다. 「계산 복잡도」라는 분야가 여기서 시작되었다. 대각선 논법으로 복잡도 종류를 가르는 방법의 뿌리를 보려는 독자에게 권한다. 미국수학회 누리집에 PDF 가 올라 있다.

    확인:미국수학회 누리집의 공개 PDF 를 열어 정리 6·정리 9 와 그 증명 요약을 읽음.
    원문 주소 (www.ams.org)
  • 교과서원문 확인
    Computational Complexity: A Modern ApproachSanjeev Arora, Boaz Barak · 2009Cambridge University Press, 2009

    계산 복잡도 이론의 표준 교재로, 학부 고학년에서 대학원 입문 수준이다. P·NP 의 정의부터 회로 하한, 대화형 증명, PCP 정리, 탈무작위화, 자연 증명까지 이 서비스의 개념 대부분을 엄밀하게 다룬다. 정의와 증명을 제대로 공부하려는 독자에게 권한다. 연결한 것은 저자들이 운영하는 책 누리집으로, 초고와 정오표가 있다.

    확인:출판본이 아니라 저자 공개 초고(2007년 1월판)의 해당 장·절을 읽음.
    원문 주소 (theory.cs.princeton.edu)
  • 개관원문 확인
    P =? NPScott Aaronson · 2017ECCC TR17-004 (2017년 1월 8일 공개) · 책 Open Problems in Mathematics (John Forbes Nash Jr., Michael Th. Rassias 엮음, Springer, 2016), 1–122쪽에 실린 글

    P 대 NP 문제의 의미와 알려진 결과, 장벽, 접근 전반을 120여 쪽에 정리한 개관이다. 수학·과학·공학 배경의 넓은 독자를 겨냥해, 왜 P ≠ NP 라고 믿는지, 왜 증명이 어려운지, 지난 반세기에 무엇이 진전되었는지를 저자의 관점과 함께 설명한다. 상대화·자연 증명·대수화 장벽과 GCT 까지 다루므로, 이 서비스의 2부를 한 편으로 깊이 읽고 싶은 독자에게 가장 먼저 권한다.

    확인:저자 공개본(2017년 판)을 열어 인용한 절들을 읽음.
    원문 주소 (www.scottaaronson.com)
  • 개관원문 확인
    The status of the P versus NP problemLance Fortnow · 2009Communications of the ACM 52(9), 78–86쪽 (2009)

    P 대 NP 문제의 의미와 2009년 시점의 연구 상황을 전산학 일반 독자에게 풀어 쓴 개관이다. 문제를 풀려던 시도들과 그 한계, NP-완전 문제를 현실에서 다루는 법, 양자 컴퓨터의 가능성까지 짧게 훑는다. 수식이 거의 없어 입문 독자가 처음 읽을 영어 글로 알맞다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 인용한 절들을 읽음.
    원문 주소 (lance.fortnow.com)
  • 보조 자료원문 확인
    Time hierarchy theoremWikipedia contributors · 2026영어 위키백과 (2026-10-05 확인)

    시간 위계 정리를 다룬 영어 위키백과 문서다. 2-4 의 시간 위계 정리 글이 Hennie–Stearns 의 개선, P ⊊ EXP 의 유도, 비결정적 판의 내력을 확인하는 보조 자료로 썼다.

    확인:위키백과 문서를 직접 열어 해당 서술을 확인(2차 자료).
    원문 주소 (en.wikipedia.org)
  • 부분 결과서지만 확인
    Two-tape simulation of multitape Turing machinesF. C. Hennie, R. E. Stearns · 1966Journal of the ACM 13(4), 533–546쪽 (1966)

    테이프가 여러 개인 튜링 기계를 두 테이프 기계로 로그 배의 비용만 치르고 흉내 낼 수 있음을 보인 논문이다. 이 결과로 시간 위계 정리의 조건이 지금의 꼴(f(n)·log f(n))로 다듬어졌다. 2-4 의 시간 위계 정리 글이 인용한다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 영어 위키백과 「Time hierarchy theorem」 문서와 Arora–Barak 공개 초고 3장으로 확인.
    원문 주소 (doi.org)DOI 10.1145/321356.321362
  • 부분 결과서지만 확인
    A hierarchy for nondeterministic time complexityStephen A. Cook · 1973Journal of Computer and System Sciences 7(4), 343–353쪽 (1973) · 학회 발표 STOC 1972, 187–192쪽

    비결정적 시간에도 위계 정리가 성립함을 처음 증명한 논문이다. 따름 결과로 NP ≠ NEXP 가 나온다. 2-4 의 부분 결과 개관과 시간 위계 정리 글이 인용한다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 3장과 영어 위키백과 「Time hierarchy theorem」 문서로 확인.
    원문 주소 (doi.org)DOI 10.1016/s0022-0000(73)80028-5
  • 부분 결과서지만 확인
    A Turing machine time hierarchyS. Žák · 1983Theoretical Computer Science 26(3), 327–333쪽 (1983)

    비결정적 시간 위계 정리의 간단한 증명을 준 논문이다. 지금 교과서에 실리는 증명이 여기서 왔다. 2-4 의 시간 위계 정리 글이 인용한다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 3장과 영어 위키백과 「Time hierarchy theorem」 문서로 확인.
    원문 주소 (doi.org)DOI 10.1016/0304-3975(83)90015-4
  • 장벽서지만 확인
    Relativizations of the P =? NP QuestionTheodore Baker, John Gill, Robert Solovay · 1975SIAM Journal on Computing 4(4), 431–442쪽 (1975)

    P = NP 가 되는 오라클과 P ≠ NP 가 되는 오라클이 모두 있음을 보인, 상대화 장벽의 원전이다. 대각선 논법처럼 상대화되는 기법만으로는 P 대 NP 를 어느 쪽으로도 풀 수 없다는 첫째 장벽이 이 논문에서 나온다. 2-2 를 읽고 원문을 확인하려는 독자에게 권한다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 정리 3.9 와 Aaronson 2017 정리 43 으로 확인.
    원문 주소 (doi.org)DOI 10.1137/0204037

하위 정보 0

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

아직 없습니다.