자원을 더 주면 정말 더 많은 일을 할 수 있는가에 대한 명백한 답, 그리고 그 한계
"자원을 두 배로 늘려 주면 풀 수 있는 문제가 정말로 늘어날까?" 이 질문에 1초도 망설이지 않고 "그럼"이라 답하고 싶지만, 형식적으로 따지자면 그리 단순하지 않다. 시간 n2로는 풀 수 없는데 n3로는 풀리는 문제가 진짜 있어야 자원의 의미가 살아난다. 그런 문제가 존재한다는 것을 어떻게 보일까?
이 강의에서 만날 위계 정리(hierarchy theorem)들은 그 답이다. 시간을 늘리면 정말로 새로운 언어가 결정 가능해지고, 공간을 늘리면 정말로 새로운 언어가 인식 가능해진다. 다만 "얼마나 늘려야 하는가"의 양적 조건이 달려 있고, 함수가 적당히 잘 행동해야 한다.
일상에서 만나는 거의 모든 "정상적인" 함수 — n2, n log n, 2n 등 — 는 두 종류 모두에 들어간다. 구성 가능성은 시뮬레이터가 시계나 자처럼 자원 한도를 셀 수 있어야 한다는 기술적 요청이다.
"f를 한 단계 키워 g로 가면, 진짜로 더 많은 언어를 결정할 수 있다"는 정확한 형태다. 왜 단순히 f(n) = o(g(n))이 아니라 f(n) log f(n)이 끼어드는지가 증명에서 자연스럽게 드러난다. 보편 시뮬레이터가 어떤 TM을 흉내 낼 때 log 인자만큼의 오버헤드가 든다는 사실이 그 출처다.
증명의 도구는 칸토어가 실수의 비가산성을 보일 때 쓴 것과 본질이 같은 대각선화다. 우리는 g(n) 시간에는 결정 가능하지만 어떤 f(n)-시간 TM도 결정할 수 없는 언어를 손수 만든다.
다음 TM D를 정의하자. 입력 ⟨M⟩ — TM M의 인코딩 — 에 대해
핵심 두 사실.
사실 1. D는 시간 O(g(n))에 동작한다. 보편 시뮬레이션의 log 오버헤드 때문에 M의 한 단계가 시뮬레이션 시 O(log f(n)) 시간이 들어, 전체 비용이 O(f(n) log f(n)) ≤ O(g(n))으로 묶인다 — 정확히 정리의 가정 f log f = o(g)가 여기서 쓰인다.
사실 2. D를 결정하는 어떤 f(n)-시간 TM M0도 존재하지 않는다. 만약 존재한다면, 충분히 큰 n에서 M0의 동작이 g(n) 시간 안에 끝나도록 할 수 있다(f log f = o(g)). 입력 ⟨M0⟩(또는 같은 언어를 결정하는 충분히 긴 인코딩)을 D에 넣으면, D의 정의에 의해 D(⟨M0⟩) = ¬M0(⟨M0⟩). 그러나 M0이 D를 결정한다면 D(⟨M0⟩) = M0(⟨M0⟩). 모순. □
시간 위계와 비교하면 조건이 깔끔하다. 그저 f(n) = o(g(n))이면 충분하고, log 오버헤드가 없다. 이유는 단순. 공간은 재사용이 자유로운 자원이라 공간 시뮬레이션의 오버헤드는 상수배에 그친다. 한 셀을 천 번 다시 쓰든 자원이 늘지 않는다. 시간은 그렇지 않다. 한 단계는 한 번이고, 시뮬레이터의 내부 데이터구조 검색에 log가 자연스레 따라붙는다.
공간 위계의 증명도 같은 골격이다. g(n) 공간 시계를 들고 ⟨M⟩ 위에서 M을 시뮬레이션하다가 공간을 초과하면 멈춘다. 결과를 뒤집어 출력. 마찬가지로 어떤 f(n)-공간 기계도 이 언어를 결정할 수 없다. 한 가지 추가 주의는 공간 한계 시뮬레이션에서 무한 루프를 피하기 위해 형태 수가 2O(g(n))로 한정됨을 이용해 시계도 함께 도는 것 — 같은 형태가 두 번 나오면 정지로 간주.
위계 정리들은 추상적으로 보일 수 있으나, 곧장 구체적인 클래스 분리로 이어진다.
이 두 분리는 직관적으로는 "그야 당연히 그렇겠지" 싶지만, 형식적인 증명을 위해서는 위계 정리의 대각선화가 반드시 필요하다는 사실을 짚어 두고 싶다. 추가로, P와 EXPTIME 사이를 채우는 클래스들 — NP, PSPACE — 가운데 어딘가에 진짜 ⊊가 일어난다는 것은 알지만, 어디인지는 모른다.
위계 정리는 같은 자원 종류 안에서 양적 차이가 클 때만 분리를 보장한다. 여기서 자연스럽게 떠오르는 한계들.
자원 종류가 다르면 직접 적용 불가. P와 NP는 모두 다항 시간이지만, 비결정성이라는 정성적 차이를 가진다. 위계 정리는 결정적 시간 안에서의 양적 분리, 비결정적 시간 안에서의 양적 분리만 직접 말해 준다. 두 종류의 시간을 가로지르는 분리는 다른 도구가 필요하다 — 그리고 그 도구가 아직 없다.
같은 종류 안에서도 격차가 작으면 무력. P vs PSPACE는 양쪽이 모두 결정적이지만, P는 다항 시간을, PSPACE는 다항 공간을 다룬다. 다항 시간 ⇒ 다항 공간이지만 그 역은 미해결. 시간과 공간을 잇는 위계는 별도의 미해결 영역이다.
릴라티비제이션 장벽. 60년대 후반 Baker–Gill–Solovay는 oracle A를 잘 골라 PA = NPA를 만들 수도, PB ≠ NPB를 만들 수도 있음을 보였다. 위계 정리의 대각선화는 oracle 아래에서도 그대로 작동한다(시뮬레이션이 oracle을 그대로 통과). 따라서 P vs NP는 단순한 대각선화 논증으로는 풀 수 없다는 강력한 신호. 이것이 relativization barrier다. P와 NP 사이의 진짜 분리(혹은 등식)는 더 정교한 도구가 필요하다는 메시지로 받아들여진다.
이 강의에서는 자원의 의미를 정량적으로 굳혔다. 시간을 한 단계 늘리면 (log 인자를 감안하고) 진짜로 새 언어가 풀리고, 공간도 마찬가지다. 그 결과 P ⊊ EXPTIME, PSPACE ⊊ EXPSPACE 같은 가장 자연스러운 분리가 안전하게 손에 들어왔다. 동시에, P vs NP, P vs PSPACE 같은 작은 격차의 클래스 분리는 위계 정리의 손이 닿지 않는 영역임을 확인했다.