1. 계산이란 무엇인가

“계산”이라는 단어는 일상에서 너무 자주 쓰여 오히려 무덤덤하게 들린다. 그러나 계산이론(theory of computation)이 던지는 질문은 결코 무덤덤하지 않다. 어떤 문제가 기계로 풀릴 수 있는가, 그리고 풀린다면 얼마만큼의 자원이 필요한가. 이 질문에 정직하게 답하려면 먼저 “기계”라는 말의 뜻부터 못박아야 한다.

철학적인 만담으로 빠지기 전에 한 가지 영리한 결정을 내려 두자. 우리는 가장 강력한 모델, 예컨대 임의 크기의 메모리를 가진 튜링 기계(Turing machine)부터 시작하지 않는다. 오히려 그 반대다. 가장 단순한 모델—메모리가 유한한 작은 기계—에서 출발한다. 단순한 세계에서 무엇이 가능하고 무엇이 불가능한지 정확히 그려낸 다음, 한 단계씩 능력을 키워 가며 그 경계가 어떻게 변하는지를 추적할 것이다. 작은 사다리부터 차례로 밟는 것이 절벽을 단번에 넘는 것보다 훨씬 멀리 데려다 준다.

그 가장 단순한 모델이 바로 유한 오토마타(finite automaton)다. 신호등의 상태 전환, 자동판매기의 잔돈 계산, 어휘 분석기의 토큰 인식—이런 것들이 본질적으로 유한 오토마타의 작동 방식이다. 너무 단순해 보일지 모르지만, 단순하다는 것은 곧 명료하게 분석할 수 있다는 뜻이기도 하다.

2. 알파벳, 문자열, 언어

기계가 다루는 입력을 형식화해 두자. 알파벳(alphabet) Σ는 유한하고 공집합이 아닌 기호들의 집합이다. 흔히 Σ = {0, 1} (이진 알파벳), Σ = {a, b}, 혹은 Σ = {a, b, ⋯, z}와 같이 쓴다. 문자열(string)은 Σ의 원소를 유한 번 이어 붙인 수열이며, 길이 0인 빈 문자열은 ε로 표기한다. 문자열 w의 길이는 |w|로 쓴다.

정의가 살짝 김빠질 수 있다. “언어”라는 거창한 단어 뒤에 숨은 것이 결국 문자열들의 집합 하나라니. 그러나 이 가벼운 정의가 무거운 일을 한다. 우리가 “문제를 푼다”라고 말하는 행위가 “주어진 입력 w가 어떤 정해진 집합 L에 속하는지 결정한다”라는 행위와 일대일로 대응되기 때문이다. 소수 판별 문제도, 문법 검사도, 컴파일러의 토큰 인식도 모두 이 형태로 다듬을 수 있다. 언어를 다루는 기계를 이해하면 결국 “문제를 푸는 기계”를 이해하게 된다.

3. 결정적 유한 오토마타(DFA)

유한 오토마타의 가장 절제된 형태부터 보자. 결정적 유한 오토마타(DFA, Deterministic Finite Automaton)는 입력 문자열을 왼쪽에서 오른쪽으로 한 글자씩 읽으며, 각 단계에서 “현재 상태”라는 하나의 정보만을 기억한다. 상태의 수는 유한하다. 다음 상태는 현재 상태와 읽은 글자에 의해 유일하게 결정되므로 이름에 “결정적(deterministic)”이라는 수식이 붙는다.

전이 함수는 이름은 거창해도 결국 “상태와 글자의 쌍을 다음 상태로 보내는 표”에 불과하다. 머릿속으로 그리려면 다음과 같은 그림이 편하다. 동그라미는 상태, 화살표는 전이, 화살표 머리에 입력 글자를 적는다. 시작 상태에는 어디서 들어오는 화살이 하나 있고, 받아들임 상태에는 이중 동그라미를 두른다.

       a            b
q0 ─────▶ q1   q0 ─────▶ q0
q1 ─────▶ q1   q1 ─────▶ q2
q2 ─────▶ q1   q2 ─────▶ q0

4. 정규 언어

이렇게 만든 모델로 표현 가능한 언어들에 이름을 붙여 두자. 이 클래스가 앞으로 몇 강의 동안 우리의 주된 무대가 된다.

정의를 보고 “DFA로만 정의되는 클래스인데 왜 이름을 따로 짓는가” 하는 의문이 들 수 있다. 그 답은 다음 두 강의에 걸쳐 자연스럽게 드러난다. 같은 클래스가 비결정적 모델로도, 정규 표현식으로도, 닫힘 연산의 결과로도 등장한다. 같은 산을 동·서·남쪽에서 각각 올라가 모두 같은 정상에 닿는 셈이다.

5. 정규 표현식

이제 같은 정상에 가는 또 다른 등산로를 살짝 엿본다. 정규 표현식(regular expression)은 언어를 구문론적으로, 즉 작은 표현식을 결합해 서서히 키우는 방식으로 정의한다.

합집합 ∪, 연결(concatenation), 그리고 클레이니 스타(Kleene star) *—이 셋이 정규 표현식의 세 가지 기본 연산이다. 같은 표현식이라도 괄호와 우선순위 약속에 따라 외양이 달라진다. 통상적으로 *가 가장 강하게 결합하고, 그 다음이 연결, 마지막이 ∪이다.

6. 다음 강의 예고

여기까지 우리는 결정적 기계와 구문적 표현식이라는 두 갈래 길을 깔아 두었다. 다음 강의에서는 길을 하나 더 추가한다. 한 상태에서 동시에 여러 곳으로 갈라질 수 있는 비결정적 유한 오토마타(NFA)가 그것이다. 처음에는 “편법 같다”는 느낌이 들겠지만, 놀랍게도 NFA가 인식할 수 있는 언어 클래스는 DFA의 그것과 정확히 같다는 사실을 증명할 것이다. 거기에 정규 표현식까지 같은 클래스로 합류하면, 정규 언어라는 한 봉우리에 세 개의 등산로가 모두 닿게 된다.

1. 비결정성이라는 사고 실험

지난 강의의 DFA는 모범생이었다. 매 단계 정확히 한 곳으로만 움직였고, 같은 입력에 대해 같은 답을 내놓았다. 이번에는 그 모범생 옆에 약간 수상한 선배 한 명을 앉혀 보자. 같은 입력 글자를 보고도 여러 상태로 동시에 갈라질 수 있는 기계, 심지어 입력을 한 글자도 읽지 않고도 상태를 바꿀 수 있는 기계. 이 선배가 바로 비결정적 유한 오토마타(NFA, Nondeterministic Finite Automaton)이다.

비결정성을 사람의 비유로 풀자면 이렇다. DFA는 길이 갈라질 때마다 한쪽을 “골라야” 한다. NFA는 그런 선택을 거부한다. 모든 갈래길에서 분신술을 써서 모든 갈래로 동시에 들어간다. 어느 한 분신이라도 끝까지 살아남아 받아들임 상태에 도달하면, 전체 NFA는 그 입력을 받아들였다고 선언한다. 한 분신이 막다른 골목에 부딪혀 사라지더라도, 다른 분신이 골인하면 그만이다.

2. NFA의 형식 정의

형식적으로 비결정성을 어떻게 표현할까. 두 가지 변화가 필요하다. 첫째, 한 상태와 한 글자에서 갈 수 있는 다음 상태가 여러 개일 수 있어야 한다. 둘째, 글자를 읽지 않고도(즉 ε으로) 이동할 수 있어야 한다.

전이 함수의 공역이 Q가 아니라 P(Q)인 점이 핵심이다. δ(q, a) = ∅이라는 것은 “이 상태에서 a를 보면 갈 곳이 없다”라는 뜻이고, 이 분신은 거기서 사라진다. 반대로 δ(q, a) = {p₁, p₂, p₃}이면 분신 셋이 동시에 태어난다.

        0,1
       ┌──┐
       ▼  │
   ──▶ q0 ──1──▶ q1 ──0,1──▶ q2 ──0,1──▶ q3((accept))

3. 부분집합 구성: NFA를 DFA로 흉내 내기

비결정성이 진짜로 새로운 능력을 추가했는가. 답은 “아니다”이다. 매 시점에 NFA의 상태가 “여러 분신의 집합”이라는 점에 착안하면, 그 집합 자체를 새로운 단일 상태로 보면 된다. 즉 NFA의 상태 집합 Q에 대해 그 멱집합 P(Q)를 새로운 DFA의 상태 집합으로 삼는다. 이를 부분집합 구성(subset construction)이라 부른다.

구성 자체는 깔끔하지만 대가가 있다. NFA의 상태가 n개라면 DFA의 상태는 최대 2ⁿ개까지 부풀 수 있다. 이를 상태 폭발(state explosion)이라 한다. 실제로 위 “끝에서 세 번째가 1” 예제에서, 부분집합 구성을 끝까지 적용하면 도달 가능한 부분집합만 따져도 2³ = 8 정도의 상태가 등장한다. NFA는 진정 새로운 능력을 가진 것이 아니라, 같은 능력을 더 압축된 형태로 표현하는 표기법인 셈이다.

4. 정규 언어의 폐쇄성

같은 클래스를 두 가지 방식으로 표현할 수 있다는 사실은 단순한 미학적 결과를 넘어선다. 어떤 연산에 대해 클래스가 닫혀 있는지 보일 때, 어느 모델이든 편리한 쪽을 골라 쓸 수 있게 되기 때문이다.

5. 정규 표현식 → NFA: 톰슨 구성

정규 표현식과 유한 오토마타가 같은 클래스를 표현한다는 큰 정리의 한쪽 방향을 처리하자. 즉 임의의 정규 표현식 R로부터 L(N) = L(R)인 NFA N을 만들 수 있음을 보인다. 정규 표현식의 정의가 귀납적이므로 구성도 귀납적이다. 이 방법을 톰슨 구성(Thompson’s construction)이라 한다.

6. 다음 강의 예고

이 시점에서 우리는 정규 언어를 향한 두 갈래 등산로—DFA/NFA와 정규 표현식—를 한쪽 방향(정규 표현식 → NFA)으로 연결했다. 다음 강의에서는 반대 방향(DFA → 정규 표현식)을 매듭짓고, 더 무거운 질문 하나를 들고 온다. 정규 언어가 아닌 언어가 존재하는가, 있다면 어떻게 증명하는가. 그 답은 비둘기집 원리가 살짝 변장한 모습으로 등장하는 펌핑 보조정리에서 나온다. 그 다음에는 한 단계 더 큰 사다리에 발을 올려, 균형 괄호처럼 정규 언어가 도저히 잡지 못하는 언어들을 잡아내는 문맥 자유 문법(CFG)으로 이행할 것이다.

1. 펌핑 보조정리: 한계의 증명서

지금까지의 강의는 “할 수 있는 것”을 늘어놓는 자리였다. 이번 절은 자세를 바꾼다. 정규 언어가 할 수 없는 일을 명시적으로 증명하기 위한 도구를 만든다. 이름은 거창하지만 그 본질은 한 줄로 요약된다. 유한한 메모리는 결국 같은 상태를 반복하게 되어 있다.

한 줄로 다시 적어 두자. 유한 상태 기계가 충분히 긴 입력을 처리하면 같은 상태를 두 번 거치게 되며, 그 사이의 부분 문자열은 마음대로 펌프질해도(반복하거나 통째로 지워도) 받아들임 여부가 변하지 않는다. 비둘기집 원리가 자동기계의 옷을 갈아입은 모습이다.

2. 비정규성의 살벌한 시범: { aⁿbⁿ : n ≥ 0 }

도구를 손에 쥐었으니 시연을 한 번 해 보자. Σ = {a, b}에서 L = {aⁿbⁿ : n ≥ 0}이 정규가 아님을 증명한다. 직관적으로 이 언어를 인식하려면 a를 몇 개 봤는지 정확히 세어 두어야 하는데, 유한 메모리로는 임의로 큰 카운터를 흉내낼 수 없다는 것이 핵심이다. 이를 펌핑 보조정리로 정밀하게 표현한다.

증명 한 토막에서 가져갈 교훈. 펌핑 보조정리는 “적이 길이 p를 골라 주면 우리가 도전 문자열 s를 골라야 한다”는 일종의 이인 게임이다. s를 영리하게 고르면(가능한 한 “나누기 어려운” 문자열로) 적이 어떻게 쪼개든 i를 적당히 골라 모순을 만들 수 있다. 이 책에서는 자주 등장하는 패턴이니 손에 익혀 두는 편이 좋다.

3. DFA → 정규 표현식: GNFA 상태 제거법

지난 강의에서 정규 표현식을 NFA로 옮기는 톰슨 구성을 보았다. 이번엔 반대 방향이다. 일반화 NFA(GNFA, Generalized NFA)를 거쳐 DFA에서 정규 표현식을 뽑아낸다.

GNFA란 화살의 라벨이 단일 글자가 아니라 임의의 정규 표현식인 NFA다. 추가로 다음 정형(normal form)을 가정해 두면 작업이 깔끔해진다.

• 유일한 시작 상태 s′가 있고, 이 상태로 들어오는 화살이 없다.
• 유일한 받아들임 상태 a′가 있고, 이 상태에서 나가는 화살이 없으며 s′ ≠ a′이다.
• s′, a′이 아닌 임의의 두 상태 사이에는 정확히 하나의 화살(라벨이 정규 표현식)이 있고, 자기 자신으로 가는 화살도 정확히 하나 있다(없는 자리는 ∅으로 라벨).

주어진 DFA M으로부터 시작 상태 s′와 받아들임 상태 a′를 새로 추가하고 ε-전이로 연결하면, 어렵지 않게 위 정형의 GNFA를 얻을 수 있다. 이제 핵심 보조 명제는 다음이다.

이 절차를 q_rip를 하나씩 골라가며 상태가 둘(시작 s′와 받아들임 a′)만 남을 때까지 반복한다. 마지막에 남은 (s′ → a′) 화살의 라벨이 곧 L(M)을 표현하는 정규 표현식이다.

이로써 우리는 정규 언어라는 봉우리에 오르는 세 등산로—DFA, NFA, 정규 표현식—가 모두 같은 정상에 닿는다는 그림을 완성했다. 펌핑 보조정리는 그 정상의 고도가 어디까지인지(즉 무엇을 못 하는지) 알려준다.

4. 더 큰 사다리: 문맥 자유 문법

{ aⁿbⁿ }이 정규가 아니라는 사실은 두 가지 반응을 부른다. 한쪽은 “그러면 됐다, 우리는 정규 언어만으로 충분하다”라고 손을 털 것이고, 다른 한쪽은 “그렇다면 그 너머를 잡아내는 더 강한 모델이 필요하다”라고 팔을 걷어붙일 것이다. 후자의 길로 들어선 첫 정류장이 문맥 자유 문법(CFG, Context-Free Grammar)이다. 균형 괄호, 산술식의 결합 구조, 프로그래밍 언어의 구문—이 모든 것이 CFG의 영역이다.

유도(derivation)란 시작 변수 S에서 규칙을 차례로 적용해 단말 문자열에 도달하는 한 편의 이야기다. 같은 단말 문자열 w를 만들어 내는 유도가 여러 가지일 수 있는데, 그중 “서로 다른 트리 모양에 해당하는” 본질적으로 다른 유도가 둘 이상 존재할 때 그 문자열은 G에서 모호(ambiguous)하다고 한다. 그리고 유도의 트리 모양 자체를 파스 트리(parse tree)라 부른다. 트리의 뿌리는 S, 내부 노드는 변수, 잎은 단말이며, 각 내부 노드의 자식들은 그 노드에서 적용된 규칙의 우변과 일치한다.

5. 다음 강의 예고

이번 강의로 정규 언어의 영토를 사방에서 둘러보고, 그 너머에 펼쳐진 문맥 자유 언어라는 새 대륙으로 첫발을 디뎠다. 다음 강의에서는 CFG에 대응하는 자동기계인 푸시다운 오토마타(PDA)를 도입해 “스택이라는 한 줄짜리 무한 메모리”가 어떤 능력을 추가해 주는지 살핀다. 그리고 CFL에도 그들만의 펌핑 보조정리(흔히 문맥 자유 펌핑 보조정리)가 있어, 이번에는 CFL이 아닌 언어의 존재—예컨대 { aⁿbⁿcⁿ }—를 증명할 무기로 사용된다는 점도 보게 될 것이다. 사다리는 아직 끝나지 않았다.

1. 스택 한 개의 차이

지난 강의에서 우리는 문맥 자유 문법(CFG)을 익혔다. 이번에는 그 문법이 만들어 내는 언어를 기계로 받아들이는 장치를 짚어 본다. 결정적 유한 오토마타(DFA)는 기억 용량이 정확히 상태 개수만큼이라, aⁿbⁿ처럼 a의 개수를 b가 다 끝날 때까지 들고 있어야 하는 문제 앞에서 무력했다. 해법은 의외로 소박하다. 카페에서 접시를 쌓아 올리듯, 오토마타 옆에 무한 스택 하나를 두는 것이다.

이 장치를 푸시다운 오토마타(pushdown automaton, PDA)라 부른다. 입력을 한 글자씩 읽으면서 스택의 맨 위(top)를 보고, 거기에 무엇을 새로 쌓을지(push) 혹은 무엇을 걷어 낼지(pop)를 결정한다. 흥미로운 점은 PDA는 본디 비결정적(nondeterministic)이라는 사실이다. 결정적 모델은 표현력을 잃기에, 처음부터 분기를 허용한다.

전이 함수가 ε을 세 자리 모두에 허용한다는 점에 주목하자. 입력을 안 읽고도 움직일 수 있고, 스택을 안 건드려도 되고, 스택에 안 쌓아도 된다. 이 자유도가 비결정적 분기를 빚어낸다.

2. 첫 예제: { aⁿbⁿ : n ≥ 0 }

고전 중의 고전. 아이디어는 단순하다. a를 읽을 때마다 스택에 표식 A를 쌓고, b가 시작되면 a 하나마다 A를 하나씩 걷어 낸다. 입력 끝에서 스택이 처음 상태로 돌아와 있으면 a와 b의 개수가 같다.

구현 디테일 하나. 스택이 비었는지 검사하는 표준 트릭은, 시작과 동시에 바닥 표시 $를 깔아 두는 것이다. 그러면 "스택이 비었음"을 직접 묻는 대신 "$가 top에 있음"을 물으면 된다.

상태:    qstart --(ε, ε → $)--> q1
         q1     --(a, ε → A)--> q1          (a를 읽고 A 푸시)
         q1     --(ε, ε → ε)--> q2          (b 단계로 비결정적 전환)
         q2     --(b, A → ε)--> q2          (b를 읽고 A 팝)
         q2     --(ε, $ → ε)--> qaccept     (바닥이 보이면 수락)

입력 a a a b b b 의 진행:
  스택        남은 입력
  $           a a a b b b
  A $         a a b b b
  A A $       a b b b
  A A A $     b b b
  A A A $     b b b      ← q1 → q2 ε-전이 (분기)
  A A $       b b
  A $         b
  $           ε
  ε           ε          ← 수락
    

"q₁에서 언제 q₂로 넘어가야 하는가"라는 결정은 비결정성에 맡긴다. 어떤 분기든 입력 끝에서 수락할 수 있는 길이 하나라도 있으면 PDA는 그 문자열을 받아들인다.

3. CFG → PDA: 유도를 스택 위에서 시뮬레이션

이제 큰 정리로 향하는 한 방향, "CFG가 만든 언어는 어떤 PDA가 인식한다"를 보자. 발상은 깔끔하다. 스택을 유도의 작업대로 쓴다. 좌측 유도(leftmost derivation)는 항상 "맨 왼쪽 비단말을 한 번 펼친다". 그러므로 스택 top에 비단말이 있으면 그것을 규칙의 우변으로 바꿔 치우면 된다.

한 번에 여러 기호를 푸시한다는 표현은 앞서 언급한 대로 ε-전이 연쇄로 풀어 쓰면 된다. 스택을 "역순으로" 쌓아야 한다는 점이 학생들이 자주 놓치는 자리다. α = X₁X₂X₃이라면 X₃을 먼저, 그 위에 X₂, 그 위에 X₁을 쌓아야 X₁이 top에 온다.

4. PDA → CFG: A_pq 비단말로 구간 분해

역방향은 한 차례 정신을 단단히 차려야 한다. 임의의 PDA가 인식하는 언어를 어떻게 문법으로 환원할 수 있을까? 그 핵심 발상은 다음과 같다.

PDA의 동작에서 한 토막을 떼어 보자. 시점 A에서 상태 p에 있고 스택의 어떤 기호 X가 top이며, 시점 B에서 상태 q에 있고 그 X가 마침내 팝되어 사라지는 순간이라고 하자. 그 사이 스택은 X를 일단 떠받친 채 위로 더 쌓였다 다시 무너져 내렸을 것이다. 즉, 시작과 끝 사이의 스택 높이는 X 위로만 변동했다. 이 구간 동안 PDA가 읽은 입력을 한 비단말 A_pq로 부르자.

일반성을 위해 PDA를 약간 표준화한다. (i) 유일한 수락 상태가 하나이고, (ii) 수락은 스택이 비었을 때만 일어나며, (iii) 모든 전이는 푸시 또는 팝 가운데 정확히 하나만 한다. 이렇게 정리하면, 임의의 수락 실행은 "처음에 무언가를 푸시 — 그 위에서 사다리꼴이 오르내림 — 결국 그것을 팝"의 형태로 분해된다.

증명은 길어 보여도 분해 원리는 한 문장이다. 스택은 결국 자기가 쌓은 것을 자기가 다 치우고 가야 한다. 그 "쌓고 치움"의 기록을 비단말 A_pq가 저장하는 것이다.

5. 동치성 정리와 결정적 PDA

두 방향의 구성을 합치면 위 정리가 된다. 이제 우리는 같은 사물을 두 가지 언어로 말할 수 있다. 문법으로 묘사하거나, 기계로 묘사하거나. 어느 쪽이 편한지는 문제마다 다르다. 폐쇄성(합집합·연결·* 연산에 대한 닫힘)은 문법 쪽이 다루기 쉽고, 인식 알고리즘과 파싱은 기계 쪽이 다루기 쉽다.

다음 강의에서는 CFL의 한계를 가르는 도구, 즉 문맥 자유 언어 펌핑 보조정리를 들고 와서 "이 언어는 CFL이 아니다"를 증명하는 법을 배운다. 그리고 마침내 스택 한 개의 천장을 뚫고, 무한 테이프라는 새 풍경 — 튜링 기계 — 으로 발을 들인다.

1. 스택 한 개의 한계를 어떻게 증명할까

정규 언어를 다룰 때 우리는 펌핑 보조정리(pumping lemma)로 한계선을 그었다. CFL에도 같은 정신의 도구가 있다. 다만 한 군데를 늘리는 정규판과 달리, 문맥 자유판은 두 군데를 동시에 부풀린다. 이유는 곧 드러난다. 충분히 긴 문자열의 파스 트리(parse tree)에는 같은 비단말이 어떤 경로 위에 두 번 등장할 수밖에 없기 때문이다.

조건 1은 v와 y를 같은 횟수만큼 동시에 늘리거나 줄여도 언어 안에 머무른다는 뜻. 조건 2는 적어도 한쪽은 비어 있지 않다는 뜻으로, "0번 펌프"가 무의미한 분할이 되는 것을 막는다. 조건 3은 v와 y가 서로 너무 멀리 떨어져 있지 못하도록 묶어 둔다.

2. 직관: 깊은 트리에는 같은 비단말이 두 번 나타난다

증명의 핵심 발상을 보자. 촘스키 정규형(Chomsky normal form)으로 옮긴 문법 G의 비단말 개수를 b개라 하고, 분기수가 최대 2인 이진 파스 트리를 생각하자. 깊이 h인 이진 트리의 잎 개수는 최대 2^h이므로, 잎이 충분히 많으면 트리도 깊어야 한다. 길이 |s| ≥ 2^b+1인 문자열의 파스 트리에는 길이 b+1을 넘는 어떤 뿌리-잎 경로가 존재하고, 그 경로 위에는 비둘기집 원리로 같은 비단말 R이 적어도 두 번 등장한다.

경로 위쪽의 R을 R_위, 아래쪽의 R을 R_아래라 하자. R_아래가 만들어 내는 부분 문자열을 x, R_위는 만들지만 R_아래는 만들지 않는 양옆의 부분 문자열을 v와 y, R_위 바깥의 좌우를 u와 z로 두면 s = u v x y z가 된다. 이제 R_위의 자리에 R_아래의 부분 트리를 끼워 넣거나(0회 펌프) R_위의 부분 트리를 자기 자신 안에 거듭 끼워 넣어(i회 펌프) 새 파스 트리를 얻는다. 모두 G의 합법적 유도이므로 u vⁱ x yⁱ z ∈ L이다. 적절한 깊이에서 같은 비단말의 두 번째 등장을 처음 발견한다고 가정하면 |v x y|를 적당한 상수 p 이하로 묶을 수 있다.

펌핑 길이 p는 보통 2^b+1 정도로 잡는다. 우리가 이 보조정리를 쓰는 데에 정확한 값은 거의 필요 없다 — 존재만 보장되면 충분하다.

3. 비-CFL 증명: { aⁿbⁿcⁿ : n ≥ 0 }

고전적인 비-CFL의 증인이다. CFG가 a와 b의 개수는 맞출 수 있어도, 거기에 더해 c의 개수까지 동시에 맞추는 것은 스택 하나로 감당이 안 된다는 직관을 펌핑 보조정리가 증명으로 굳혀 준다.

같은 기법으로 { ww : w ∈ {0,1}* } 또한 비-CFL임이 보인다. 이쪽은 분할 자리를 따라가며 케이스 분석을 좀 더 신중하게 해야 한다.

4. 무한 테이프로 한 발 나아가다 — 튜링 기계

스택 한 개의 천장이 보였으니, 천장을 들어 올릴 차례다. 답은 의외로 단순하다. 읽기 전용 입력 테이프와 따로 떨어진 스택 대신, 읽고 쓰는 한 줄짜리 무한 테이프를 두자. 헤드(head)가 좌우로 자유로이 움직이며 어떤 칸이든 다시 들여다볼 수 있다. 이것이 1936년 앨런 튜링이 그린 그림이다.

테이프는 양쪽 또는 한쪽으로 무한히 뻗어 있다 — 어느 쪽으로 정의하든 표현력은 같다. 입력은 처음에 테이프의 왼쪽 끝부터 차례로 적혀 있고, 그 뒤로는 모두 빈칸 ␣이다. 헤드는 입력의 첫 칸을 본 채로 시작한다.

초기 테이프와 헤드:

   ⌊ 0 0 1 1 ␣ ␣ ␣ ␣ ⌋ ...
     ^
     헤드, 상태 q0
    

5. 구성, 계산, 그리고 세 가지 결말

한 시점에 TM이 무엇을 하는지 적어 두려면 세 정보가 필요하다. (i) 현재 상태, (ii) 테이프 내용, (iii) 헤드의 위치. 이 셋을 묶어 구성(configuration)이라 부르고, "상태 기호 직전에 끼워 넣은 한 줄"의 표기 u q v로 압축한다 — 헤드는 v의 첫 칸을 본다는 뜻이다.

한 구성에서 다음 구성으로 한 걸음 옮아가는 관계를 ⊢로 적는다. 시작 구성에서 출발해 ⊢로 이어지는 (유한 또는 무한) 열을 계산(computation)이라 한다. 계산의 결말은 정확히 셋이다.

• q_accept에 들어가면 즉시 멈추고 수락한다.
• q_reject에 들어가면 즉시 멈추고 거부한다.
• 둘 다 들지 않으면 영원히 굴러간다 — 무한 루프.

차이는 단어 하나에 있다. "수락하지 않음"이 "거부로 멈춤"인지 아니면 "멈추지 않을 수도 있음"인지. 이 한 끗의 간격이 다음 강의들의 풍경을 거의 다 결정짓는다.

6. 첫 TM 예제: { 0ⁿ1ⁿ : n ≥ 0 } 결정하기

테이프와 좌우 이동의 위력을 가장 단순한 예에서 맛보자. 우리는 0과 1의 개수가 같은 언어 { 0ⁿ1ⁿ }이 결정 가능함을 직접 TM을 만들어 확인한다. (이 언어는 CFL이지만, 결정 가능하기도 하다.)

시작:        ⌊ 0 0 1 1 ␣ ⌋   상태 q0, 헤드는 첫 0
1회 한 쌍:  ⌊ X 0 1 Y ␣ ⌋   상태 q왼쪽, 헤드는 X
2회 한 쌍:  ⌊ X X Y Y ␣ ⌋   상태 q점검, 헤드는 첫 X
점검 통과:  ⌊ X X Y Y ␣ ⌋   상태 qaccept → 수락
      

좀 더 야심 찬 예로 { wcw : w ∈ {0,1}* }를 들 수 있다. 이쪽은 c 양쪽의 두 부분이 글자별로 같은지 비교해야 한다. 한 글자씩 표식을 남기며 좌우를 오가는 동작은 TM의 자유로운 헤드 움직임이 없으면 흉내 내지 못한다 — 어떤 PDA로도 결정할 수 없는 언어다.

7. 다음 풍경 — Church-Turing 명제

튜링 기계의 정의는 미니멀하다. 그러나 다중 테이프, 비결정성, 이차원 테이프, 무작위 접근 같은 어떤 변종을 가져다 붙여도 결정 가능한 언어 부류는 변하지 않는다. 더 놀라운 사실은 람다 대수, μ-재귀 함수, 마르코프 알고리즘 등 전혀 다른 출발점에서 시작된 계산 모형들이 모두 같은 언어 부류를 결정한다는 것이다. 이 합치를 한 문장으로 요약한 것이 Church-Turing 명제다 — 직관적으로 "알고리즘으로 풀 수 있는 문제"란 정확히 튜링 기계가 결정할 수 있는 문제이다.

다음 강의부터는 이 무한 테이프 기계 위에서 결정 가능한 문제들을 사냥하고, 결정 불가능한 영역의 첫 표본 — 정지 문제 — 을 향해 다가간다. 펌핑 보조정리가 우리에게 "할 수 없음"의 첫 맛을 보여 주었다면, 다음에 만날 대각화는 그 맛을 한층 깊이 다듬어 줄 것이다.

1. 변형이라는 유혹

지난 강의에서 정의한 단일 테이프 결정적 튜링 기계(deterministic Turing machine, DTM)는 분명 강력하지만, 그 위에서 알고리즘을 직접 짜본 사람이라면 누구나 한 번쯤은 이렇게 외친다: "테이프 하나로는 못 해 먹겠다." 입력은 그대로 두고 작업 공간은 따로 쓰고 싶고, 결과는 또 다른 곳에 적고 싶다. 갈래마다 다른 추측을 시도해보고 싶고, 때로는 입력을 받지 않고 그냥 모든 출력을 토해내는 기계가 더 자연스럽기도 하다.

이 강의의 결론은 한 문장으로 요약된다: 이 모든 변형은 표준 단일 테이프 TM과 동치이다. 표현력은 같지만 사고의 편의는 천양지차이므로, 우리는 앞으로 증명에서 가장 편한 모델을 골라 쓸 권리를 얻는다. 그리고 이 권리의 철학적 일반화가 바로 처치-튜링 명제(Church-Turing thesis)이다.

2. 다중 테이프 튜링 기계

S(정지) 옵션이 등장했다고 당황할 필요는 없다. 우리는 곧 이 모델을 단일 테이프 모델로 시뮬레이션하면서 어차피 표현력이 같음을 보일 것이고, 실제로 단일 테이프 모델에서도 두 단계로 쪼개면 정지를 흉내 낼 수 있다.

3. 비결정적 튜링 기계

4. 열거기와 인식 가능성의 또 다른 얼굴

5. 처치-튜링 명제

지금까지 살펴본 변형은 빙산의 일각이다. 사람들은 "현실적인 계산 모델"이라 부를 만한 거의 모든 것을 정의해보았다.

• 람다 계산(λ-calculus). 알론조 처치(Alonzo Church)가 1930년대에 정의한, 순수 함수 추상화와 적용만으로 이루어진 형식 체계. 모든 계산을 함수 (λx.x) 같은 항으로 표현한다.
• 회귀 함수(recursive functions). 괴델-에르브랑-클레네의 부분 회귀 함수 클래스. 0, 후행자, 사영, 합성, 원시 회귀, 최소화 연산자(μ-operator)로 닫힌 함수들의 모임.
• 무제한 레지스터 머신(unlimited register machine, URM). 자연수 레지스터 무한 개와 증가·감소·점프 명령으로 동작하는 추상 컴퓨터. 셰퍼드슨-스터지스가 정리한 모델이다.
• 마르코프 알고리즘, 태그 시스템, 회로 패밀리, 세포 자동자(cellular automaton) 등.

놀랍게도 이 모든 모델은 정확히 같은 함수 클래스 — 부분 회귀 함수, 곧 튜링 계산 가능 함수 — 를 정의한다. 1936년 처치와 튜링은 이 사실을 다음 명제로 결정화했다.

이것은 정리가 아니다. 좌변의 "직관적"이라는 말 때문에 수학적으로 증명할 대상이 아니라, 직관적 개념과 형식적 개념을 동일시하자는 명제이자 약속이다. 그러나 90년이 지난 지금도 어떤 반례도 발견되지 않았고, 위에서 본 다양한 모델들의 등가성이 강력한 경험적 증거를 제공한다. 우리는 이제 "어떤 알고리즘이 존재한다"는 진술을 "어떤 튜링 기계가 존재한다"로 자유로이 바꿔 쓸 수 있는 면허를 갖게 된다.

6. 모델은 옷이고 알고리즘은 사람이다

강의를 마치며 한 가지만 기억하자. 단일 테이프든, 다중 테이프든, 비결정적이든, 람다 항이든, 우리가 "이것은 알고리즘이다"라고 부를 수 있는 것은 어떤 모델에서 표현해도 같은 함수를 계산한다. 모델은 알고리즘에 입히는 옷이다. 옷이 다양해도 사람은 한 명이다.

이것이 이론적으로 의미하는 바는 분명하다. 다음 강의부터 우리는 "결정 가능"과 "결정 불가능"을 자유롭게 말할 것인데, 이 개념들은 어떤 모델을 골라도 변하지 않는다. 다음 강의에서는 이 자유를 활용해 정규 언어와 문맥 자유 언어에 대한 수많은 결정 문제를 — 의외로 평이하게 — 알고리즘으로 풀어낼 것이다. 이후 강의 8에서 비로소 결정 불가능의 첫 풍경을 만나게 된다.

1. 결정 문제라는 장르

결정 문제(decision problem)란 예/아니오로 답이 떨어지는 질문이다. 우리는 이 질문들을 언어로 인코딩한다. 예컨대 "DFA B가 문자열 w를 수락하는가?"는 다음 언어의 멤버십 문제와 같다.

A_DFA = { ⟨B, w⟩ : B는 DFA이고 B가 w를 수락한다 }

여기서 ⟨B, w⟩는 DFA B의 형식적 표현과 입력 w를 한 문자열로 인코딩한 것이다. 어떤 인코딩 규약이든 — 예컨대 상태와 전이 함수를 ASCII 표로 적고 # 같은 구분자로 잇든 — 합리적이기만 하면 결정 가능 여부는 바뀌지 않는다(처치-튜링 명제의 일상적 활용 사례다).

이번 강의의 모든 정리는 같은 골격을 따른다: "어떤 TM이 입력을 받아 알고리즘적 절차를 수행하고 항상 멈추며, 답이 예일 때 정확히 수락한다." 이러한 TM이 존재함을 보이면 해당 언어는 결정 가능(decidable)이다.

2. A_DFA: 시뮬레이션 한 번이면 끝

이 증명은 거의 무의미해 보일 정도로 평이하다. 그러나 메시지는 분명하다: 유한한 자원만으로 정의되는 모델을 흉내 내는 일은 항상 결정 가능하다. 이 패턴이 이번 강의 절반의 동력이 된다.

3. E_DFA: 그래프 탐색의 변장

E_DFA = { ⟨B⟩ : B는 DFA이고 L(B) = ∅ }

DFA가 어떤 문자열도 수락하지 않는다는 것은, 시작 상태에서 어떤 수락 상태에도 도달할 수 없다는 것과 동치이다. 그리고 도달 가능성은 그래프에서 너비 우선 탐색(BFS)이면 된다.

4. EQ_DFA: 대칭차의 마법

EQ_DFA = { ⟨A, B⟩ : A, B는 DFA이고 L(A) = L(B) }

두 언어가 같음을 직접 비교하는 것은 어렵다 — 무한히 많은 문자열에 대해 일치를 확인해야 할 것 같다. 하지만 집합론적 정체성 하나로 문제가 단번에 풀린다.

L(A) = L(B) ⟺ (L(A) ∖ L(B)) ∪ (L(B) ∖ L(A)) = ∅

이 우변에 등장하는 집합을 두 언어의 대칭차(symmetric difference)라 부르고 L(A) △ L(B)로 적는다. 두 언어가 다르면, 한 쪽에는 있고 다른 쪽에는 없는 어떤 문자열이 반드시 존재한다 — 그 문자열이 대칭차에 들어 있다.

5. NFA와 정규 표현식: 변환 한 단계 추가

A_NFA = { ⟨N, w⟩ : N이 w를 수락 },    E_NFA = { ⟨N⟩ : L(N) = ∅ }

변환의 비용(상태 수가 지수적으로 폭발할 수 있음)은 결정 가능성에는 영향을 주지 않는다. 결정 가능성은 "유한 시간 안에 답이 나오느냐"의 문제이지 "얼마나 빠르냐"의 문제가 아니다. 후자는 복잡도 이론의 영역이다.

6. 문맥 자유 문법으로

A_CFG = { ⟨G, w⟩ : CFG G가 w를 생성 }

여기서 첫 번째 함정이 등장한다. 순진하게 "G가 가능한 모든 유도(derivation)를 시도해보자"고 하면 끝없이 늘어나는 유도가 무한히 많을 수 있어 절차가 멈추지 않는다. 그러나 한 가지 관찰로 문제가 풀린다.

모든 CFG는 같은 언어(필요시 ε 처리만 분리)를 생성하는 어떤 CNF로 알고리즘적으로 변환할 수 있다(보조 변수 도입, 단위 규칙 제거, ε 규칙 제거 단계의 조합). 이제 결정적 사실 하나가 마법을 부린다.

이유는 직관적이다. CNF에서 단말은 "A → a" 규칙으로만 나타나므로 길이 n인 문자열에는 단말 규칙이 정확히 n번 적용된다. 비단말 규칙 "A → BC"는 변수 한 개를 두 개로 늘리므로 변수 수를 1 증가시킨다. 시작 변수 1개에서 출발해 변수 n개까지 늘리려면 정확히 n − 1번 적용되어야 한다. 합치면 (n − 1) + n = 2n − 1.

실용적인 사람들은 단계 3을 그렇게 야만적으로 짜지 않는다. 동적 계획법으로 만든 CYK(Cocke-Younger-Kasami) 알고리즘은 O(n³)시간에 같은 문제를 푼다 — 길이 k의 모든 부분 문자열이 어떤 변수에서 유도되는지를 작은 k부터 채워 올라간다. 결정 가능성을 보이는 데에는 야만적인 나열로 충분하지만, 컴파일러를 짤 때는 CYK 또는 LR(1) 같은 더 빠른 파싱이 등장한다.

7. E_CFG: 단말 도달 가능성

E_CFG = { ⟨G⟩ : CFG G이고 L(G) = ∅ }

이 문제도 도달 가능성의 변장이다. 다만 이번 그래프는 변수와 규칙의 그래프다.

8. 풀 수 없는 한 가지: EQ_CFG

여기까지 보면 도구를 충분히 갖춘 듯 느껴진다. 그러면 EQ_CFG = { ⟨G₁, G₂⟩ : L(G₁) = L(G₂) }도 같은 트릭으로 풀릴까? 두 문맥 자유 언어의 대칭차도 결정 가능한 비어 있음 검사로 환원할 수 있을까?

아쉽게도 안 된다. 문맥 자유 언어는 합집합과 연쇄에는 닫혀 있지만 교집합과 여집합에는 닫혀 있지 않다. 따라서 대칭차 트릭이 무너진다. 이것은 단순히 우리의 구성이 통하지 않는다는 뜻이지만, 더 깊은 진실은 다음과 같다.

이 정리의 증명은 환원(reduction) 기법을 본격적으로 다룬 뒤에야 가능하다. 한편 모든 문맥 자유 언어가 (CYK가 보여주듯) 결정 가능한 멤버십을 가지므로 EQ_CFG는 결정 가능 언어 사이의 동치 문제다. 결정 가능 언어 두 개의 동치성마저 일반적으로는 결정 불가능할 수 있다는 사실을 살짝 미리 들고 가자.

9. 다음 강의로

지금까지 우리는 결정 가능의 풍요로운 정원을 거닐었다. 거기에는 시뮬레이션, 그래프 탐색, 곱 구성, 정규형 변환 같은 점잖은 도구들이 있었다. 다음 강의 8에서는 정원의 담장을 처음으로 넘는다 — 결정 불가능한 언어가 존재함을, 심지어 우리에게 가장 친숙한 질문 "M이 w를 수락하는가?"가 일반적으로는 알고리즘으로 풀리지 않음을 보일 것이다. 도구는 단 하나, 칸토어의 대각선 논법이다.

1. 무대 설정: 가산과 비가산

결정 불가능한 문제가 존재한다는 사실의 가장 우아한 증명은 단 한 줄짜리 개수 세기다. "알고리즘은 가산(countable)이다. 그러나 언어는 비가산(uncountable)이다. 그러므로 알고리즘이 짝지어줄 수 없는 언어가 — 사실은 거의 모든 언어가 — 존재한다." 이 직관을 정리해두자.

이 한 번의 대각선화를 우리는 이 강의에서 두 번 더 본다. 형태는 늘 같다: "모든 후보가 나열되었다고 가정하고, 그 나열의 대각선을 비틀어 새로운 대상을 만들어 모순을 일으킨다."

2. 인식 불가능 언어의 존재

이제 위 정리를 계산이론으로 옮긴다.

아름답지만 답답한 증명이다. "그래서 그 인식 불가능 언어가 무엇인가?"에 답하지 못한다. 다음 절에서 우리는 구체적으로 흥미로운 결정 불가능 언어를 손에 쥐게 된다.

3. A_TM: 보편 시뮬레이터의 한계

A_TM = { ⟨M, w⟩ : M은 TM이고 M이 w를 수락한다 }

U의 존재가 곧 "프로그램으로서의 컴퓨터"라는 폰 노이만식 패러다임의 이론적 토대다. 그러나 U가 인식자일 뿐 결정자는 아니라는 점이 결정적이다. 다음 정리가 그 이유를 알려준다.

4. 보조정리: 인식과 여인식의 결합

다음 절로 가기 전에 작은 보조정리 하나가 필요하다. 이는 인식 가능성과 결정 가능성 사이의 다리다.

대우 형태로 읽으면 더 강력하다: L이 인식 가능이고 결정 불가능이면, L은 인식 가능조차 아니다.

5. A_TM의 여집합: 인식 불가능의 첫 사례

이 정리에서 인식 가능 언어의 클래스(통상 RE 또는 R_e로 표기)는 여집합 아래에서 닫혀 있지 않다는 사실이 따라온다. 정규 언어와 결정 가능 언어와는 달리, 인식 가능 언어 한 개를 뒤집으면 클래스 밖으로 튀어나갈 수 있다. 이 비대칭이 결정 가능과 인식 가능을 가르는 가장 깊은 차이다.

6. HALT_TM: 환원 기법의 첫 시연

HALT_TM = { ⟨M, w⟩ : M이 w에 대해 (수락이든 거부든) 멈춘다 }

이 증명에 등장한 작은 패턴 — "B의 결정자가 있으면 A의 결정자를 만들 수 있다, 따라서 A가 결정 불가능이면 B도 결정 불가능" — 이 다음 강의의 주인공인 매핑 환원(mapping reduction)의 비공식 형태다. 환원은 결정 불가능성을 한 문제에서 다른 문제로 옮겨 심는 묘목 이식 기술이며, 우리는 이미 그 첫 한 그루를 심었다.

7. 풍경 정리와 다음 강의

이번 강의에서 본 그림을 한 장으로 정리하자. 모든 언어의 우주 𝒫(Σ*) 안에는 다음과 같은 동심원이 있다.

• 가장 안쪽: 정규 언어 ⊊ 문맥 자유 언어 ⊊ 결정 가능 언어.
• 그 다음: 인식 가능 언어. 결정 가능 언어를 진정으로 포함한다(포함 사례: A_TM).
• 밖: 인식 불가능 언어. 결정 가능 + 인식 가능을 합쳐도 채울 수 없다(포함 사례: A_TM).
• 그리고 사실은, 정리 8.4가 말하듯 거의 모든 언어가 가장 바깥 동심원에 산다 — 알고리즘은 가산이지만 언어는 비가산이므로.

다음 강의에서는 환원 기법을 정식화한다. HALT_TM의 증명에서 본 비공식 환원을 매핑 환원으로 다듬고, 그 도구로 E_TM(공어 문제), EQ_TM(동치 문제), 그리고 — 충격적이게도 — 라이스의 정리(Rice's theorem)를 만나게 된다. 라이스 정리는 한 문장으로 요약된다: "튜링 기계가 인식하는 언어의 어떤 비자명한 성질도 결정 불가능이다." 결정 불가능의 풍경이 얼마나 광대한지를 보여주는 정리다.

1. 환원이라는 사고방식

지난 강의에서 우리는 A_TM = { ⟨M, w⟩ : M이 w를 수락한다 }가 결정 불가능함을 대각선 논법으로 증명하였다. 그러나 결정 불가능한 문제가 세상에 단 하나뿐일 리는 없다. 만약 어떤 새로운 문제 B를 마주쳤을 때 또다시 대각선 논법을 처음부터 펼쳐야 한다면, 이론은 매우 비효율적인 학문이 될 것이다. 다행히 우리에게는 더 영리한 무기가 있다 — 바로 환원(reduction)이다.

환원의 직관은 이중적이다. 한편으로는 "어려운 문제를 쉬운 문제로 풀어버리기"이고, 다른 한편으로는 "쉬운 문제의 결정 불가능성을 어려운 문제로 끌어올리기"이다. 일상에서 길을 잃었을 때 우리는 도로 주소를 GPS 좌표로 환원해 길찾기 알고리즘에 넘긴다. 알고리즘 설계자에게 환원은 도구이지만, 결정 불가능성을 증명하려는 우리에게 환원은 무기다. 만약 A를 푸는 일이 B를 푸는 일로 변환된다면, B를 푸는 기계가 있을 경우 A도 풀 수 있다. 따라서 A가 풀리지 않는다면 B도 풀릴 수 없다. 한 줄의 대우가 결정 불가능성을 폭포처럼 퍼뜨린다.

2. 매핑 환원의 정의

여러 종류의 환원 가운데 가장 깔끔한 것이 매핑 환원이다. 입력을 입력으로 변환하는 단순한 함수 하나로 모든 의미가 끝난다.

핵심은 동치(⇔)이다. 단순히 "w가 A에 있으면 f(w)가 B에 있다"만 보장하면 부족하다. 반대 방향, 즉 "w가 A에 없으면 f(w)도 B에 없다"가 함께 성립해야 환원이 의미를 갖는다. 이 양방향 보장이 없다면 환원은 정보를 잃어버린 데이터 압축에 불과하다.

3. HALT_TM — 정지 문제

가장 유명한 결정 불가능 문제, 정지 문제부터 시작한다.

주목할 만한 트릭이 있다. M'은 M이 거부할 때 일부러 영원히 루프에 빠진다. "이상하다 — 거부도 정지의 한 형태가 아닌가?"라고 물을 수 있다. 그렇다. 그래서 우리가 HALT를 가두려면 거부를 "비정지"로 바꿔야 한다. 환원이란 본질적으로 의미를 약간씩 비틀어 모양을 맞추는 일이다.

4. E_TM — 빈 언어 문제

빈 언어 문제는 환원의 방향성을 흥미롭게 보여준다. 자연스럽게 시도하면 A_TM ≤_m E_TM를 보이고 싶지만, 막상 만들면 부등호 방향이 뒤집어진다. 그래서 우리는 차라리 A_TM의 여집합과 E_TM를 연결한다.

5. REGULAR_TM — TM이 정규 언어를 생성하는가

이 문제는 일견 풀릴 법도 하다. 우리에게는 펌핑 보조정리도 있고, DFA의 깔끔한 구조도 있지 않은가. 그러나 임의의 TM에 대해 그 인식 언어가 정규인지 묻는 일은 결정 불가능하다.

6. EQ_TM — 두 TM이 같은 언어를 인식하는가

이 환원의 매력은 뻔뻔스러운 단순함에 있다. 빈 언어 검사기가 있다면 동치성 검사기는 자명하게 만들 수 있고, 동치성 검사기가 있다면 빈 언어 검사기도 마찬가지다. 두 문제는 사실상 같은 문제의 두 얼굴이다.

7. 라이스 정리 — 의미의 결정 불가능성

지금까지 본 모든 결정 불가능 문제는 공통점이 있다. REGULAR, E, EQ — 모두 TM의 코드가 아니라 그 의미(언어)에 관한 질문이다. 라이스(Henry G. Rice)는 1953년 이 패턴을 정리 하나로 일반화하였다.

다시 말해, "TM이 어떤 성질의 언어를 받아들이는가"라는 형태의 질문은 — 그 성질이 자명한 두 극단(아무것도 아니거나 모든 것)이 아닌 한 — 알고리즘으로 결코 답할 수 없다.

8. 마무리

환원이라는 한 단어로 우리는 결정 불가능성의 행성계 전체를 그릴 수 있게 되었다. A_TM이 태양이라면, HALT_TM·E_TM·REGULAR_TM·EQ_TM은 그 주위를 도는 행성들이다. 라이스 정리는 더 멀리, "TM의 의미적 성질이라면 무엇이든"이라는 광활한 영역을 한꺼번에 어둠 속으로 밀어 넣는다. 다음 강의에서는 환원의 도구함을 한 단계 키운다 — 계산 이력이라는 강력한 무기를 손에 넣고 LBA, CFG, 도미노 게임에까지 결정 불가능성의 영향을 확장한다.

1. 시간을 문자열로 묶다

지난 강의의 환원들은 대체로 "M이 무언가 수락하면 ~을 한다" 식의 한 줄 트릭으로 끝났다. 그러나 우리가 결정 불가능성을 더 작고 더 약한 계산 모델로 — 예를 들어 선형 유계 오토마타(LBA)나 문맥 자유 문법(CFG)으로 — 가져가려 할 때, 그런 트릭만으로는 부족하다. 이 모델들은 임의의 튜링 기계를 시뮬레이션할 만큼 똑똑하지 않기 때문이다.

해법은 의외다. 우리는 시간을 문자열로 펼친다. TM의 계산 한 번 — 시작에서 끝까지 — 을 통째로 하나의 문자열로 적어두면, 그 문자열을 검사하는 일은 훨씬 단순한 모델로도 가능해진다. 이 기법을 계산 이력 방법(computation history method)이라 부른다. 시간이 약점이라면 시간을 공간으로 환산해버리자는 것이다.

핵심 관찰은 이렇다. M이 w를 수락하는가 묻는 것은 곧 "C₀에서 시작해 한 단계씩 합법적으로 옮겨가며 수락 구성에 도달하는 시퀀스가 존재하는가"를 묻는 것과 같다. 그리고 "한 단계 합법성"은 굉장히 국소적인 검사이다 — C_i와 C_i+1이 헤드 주변 두세 글자만 다르고 나머지는 동일하면 된다. 국소성은 약한 모델이 다룰 수 있는 친구이다.

2. 선형 유계 오토마타

LBA는 강력하다 — 모든 문맥 의존 언어를 인식한다. 그러나 동시에 약한 면도 있다. 사용 가능한 공간이 입력으로 제한되므로, 가능한 구성의 수가 유한하다. 이 유한성이 모든 차이를 만든다.

여기까지는 LBA가 다른 어떤 TM 종류보다도 다루기 쉽다는 좋은 소식이다. 그러나 LBA의 보다 풍부한 질문은 — 마치 TM에서처럼 — 곧장 결정 불가능 영역으로 들어간다.

3. E_LBA — LBA가 빈 언어를 인식하는가

4. ALL_CFG — CFG가 모든 문자열을 생성하는가

이번에는 도구를 한 단계 더 약화시킨다 — 문맥 자유 문법으로.

증명의 핵심은 영리한 뒤집기이다. CFG는 일반적으로 "잘못된 계산 이력"의 집합 — 합법적이지 않은 시퀀스의 모임 — 을 표현할 수 있다. 그러면 "잘못된 이력의 집합이 Σ* 전부인가"라는 질문은 "올바른 이력이 단 하나도 없는가"와 같고, 이는 곧 "M이 w를 거부하는가"이다.

5. Post 대응 문제(PCP)

마지막으로, 계산과는 전혀 관련 없어 보이는 — 도미노 퍼즐의 — 문제를 본다.

6. 마무리

계산 이력은 시간이라는 추상을 문자열이라는 구체로 끌어내리는 망원경이다. 이 망원경 하나로 우리는 LBA의 빈 언어, CFG의 만물 언어, 그리고 도미노 퍼즐까지 결정 불가능 영역으로 끌어들였다. 다음 강의에서는 정반대 방향의 마법을 본다 — 자기 자신을 출력하는 프로그램, 그리고 그로부터 나오는 우아한 회귀 정리이다.

1. 자기 자신을 출력하는 프로그램

다음과 같은 작은 도전이 있다. 입력 없이 실행했을 때 자기 자신의 소스 코드를 그대로 출력하는 프로그램을 작성하라. "그냥 파일을 읽으면 되지 않나?" 하는 학생도 있을 것이다. 그러나 그건 반칙이다 — 외부 자원에 접근하지 말고, 코드 자체의 글자만으로 그 코드 전체를 재구성해야 한다. 이런 프로그램을 콰인(quine)이라 부른다.

처음 시도하면 곧 무한 회귀에 빠진다. 코드를 출력하려면 그 코드를 어딘가에 적어둬야 하는데, 그 적어둔 부분도 출력해야 하므로 또 적어두고 — 마치 거울 두 개를 마주 보게 한 듯하다. 그러나 콰인은 가능하다. 그리고 콰인의 일반화가 바로 회귀 정리(recursion theorem)이다. 회귀 정리는 단지 호기심 차원의 트릭이 아니라, 임의의 튜링 기계가 "자기 자신의 기술(description)에 접근할 수 있다"는 강력한 결론을 보장한다.

2. 자신의 기술을 출력하는 TM의 보조정리

회귀 정리의 핵심은 두 단계 구성이다. 우리는 먼저 "어떤 고정된 문자열 t를 출력하는 기계"를 만드는 일반적인 절차가 존재함을 본다. 그런 다음 이 절차를 자기 자신에게 적용하여 콰인을 얻는다.

이는 직관적으로 자명하다. q는 단순히 "t를 테이프에 쓰고 정지"라는 코드를 t의 글자 수에 맞게 펼쳐 적기만 하면 된다. q 자체도 짧은 알고리즘이다.

이 두 단계 구성은 이론과 실제 양쪽에서 우아하다. A는 "B를 테이프에 적는다"는 단 한 가지 일을 하고, B는 "지금 적힌 것이 곧 무엇을 출력해야 할지를 말해주는 명세"라고 간주하여 그 명세에 따라 자기 자신을 출력한다. 콰인 작성 대회의 우승작들은 모두 이 패턴의 변주이다.

3. 회귀 정리

회귀 정리의 미덕은 "괜히 만들어진 자기 참조" 같은 인상에도 불구하고 어디에서나 등장한다는 점이다. 이제 그 위력을 두 가지 응용으로 본다.

4. 응용 1 — A_TM의 회귀 정리 증명

대각선 논법으로 A_TM의 결정 불가능성을 보였던 기억이 있을 것이다. 이제 회귀 정리를 활용하면 같은 결과를 한층 직접적이고 짧게 얻을 수 있다.

5. 응용 2 — MIN_TM은 인식 가능하지 않다

회귀 정리는 결정 불가능성보다 한 단계 더 강한 결론도 즉시 준다. "최소 길이 TM"의 집합을 보자.

이 증명에서 회귀 정리가 한 일은 단 하나 — C가 자기 자신의 길이를 알 수 있게 해준 것이다. "내가 얼마나 긴지 모르는 기계"는 "나보다 긴 것을 기다리겠다"고 말할 수 없다. 자기 참조가 길이 비교를 가능하게 했고, 길이 비교가 모순을 만들었다.

6. 1차 논리와 산술의 결정 가능성

강의의 마지막 한 발을 더 내디뎌, 회귀 정리가 빛을 발하는 또 다른 무대 — 수리논리학의 결정 문제 — 를 살핀다.

"이 문장이 자연수에서 참인가?"라는 질문은 매우 자연스러운 결정 문제이다. 그 답은 — 놀랍게도 — 어떤 연산 기호를 허용하느냐에 따라 극과 극으로 갈린다.

덧셈만 있는 자연수의 1차 논리는 — ∀, ∃, ∧, ∨, ¬와 = 만 결합한 임의의 문장이라도 — 알고리즘으로 참·거짓을 판정할 수 있다. 증명은 양화사 제거(quantifier elimination)에 의존한다 — 모든 문장을 양화사 없는 문장으로 동치 변환할 수 있고, 양화사 없는 문장은 산술 식의 단순 검사로 끝난다.

7. 마무리

강의 9에서 11까지의 흐름을 한 문장으로 요약하면, "결정 불가능성은 한 점에서 시작해 환원으로 퍼지고, 자기 참조에서 절정에 닿는다"이다. 콰인이라는 작은 장난감이 어떻게 괴델의 결과까지 끌어내는지 보았다. 다음 강의부터는 시선을 결정 가능한 영역으로 다시 돌려 — 결정 가능하지만 얼마나 효율적으로 결정 가능한가 — 라는 새로운 질문, 즉 복잡도 이론(complexity theory)으로 들어간다.

1. 결정 가능만으로는 부족하다

지난 강의들에서 우리는 어떤 언어가 결정 가능한지(decidable)를 끈질기게 따졌다. 그러나 결정 가능하다는 사실은 언젠가는 끝난다는 약속일 뿐, 그 끝이 다음 화요일인지 우주의 열사망 이후인지에 대해서는 한 마디도 하지 않는다. 이론적으로 풀 수 있다는 것과 실제로 답을 받아볼 수 있다는 것 사이에는 천지 차이가 있다.

예컨대 입력 길이 n에 대해 2ⁿ단계가 걸리는 알고리즘이 있다고 하자. n = 100이면 2¹⁰⁰ ≈ 10³⁰이다. 1나노초에 한 단계씩 처리한대도 약 10¹³년이 걸린다. 우주의 추정 나이가 1.4 × 10¹⁰년이니, 우주가 천 번쯤 다시 태어나는 동안 답을 기다려야 한다. 이런 알고리즘을 가지고 “문제가 풀린다”고 말하는 건 윤리적으로 곤란하다.

그래서 이번 강의부터는 자원(resource), 그중에서도 시간이라는 자원을 정량적으로 다룬다. 핵심 질문은 단순하다. 입력이 커질 때 실행 시간이 얼마나 빨리 자라는가?

2. 점근 표기법: 빅-O와 그 친척들

알고리즘의 실행 시간을 정확한 단계 수로 비교하는 일은 헛수고에 가깝다. 컴파일러, 기계, 테이프 알파벳에 따라 상수 배수는 얼마든지 달라지기 때문이다. 우리가 신경 쓰는 것은 큰 입력에서의 성장률이다. 그래서 점근 표기(asymptotic notation)가 등장한다.

예를 들어 3n³ + 5n + 12 = O(n³) = Θ(n³)이다. n log n = o(n²)이지만 n log n ≠ O(n)이다. 점근 표기에서 로그의 밑은 보통 표시하지 않는다 — 밑이 바뀌면 상수 배수만 달라지므로 빅-O 안에서는 차이가 사라진다.

3. TIME 클래스와 P

점근 표기를 무기로 들고 시간 복잡도 클래스를 정의한다. 모델은 일단 결정적 단일 테이프 튜링 기계(deterministic single-tape Turing machine)로 못 박는다.

P가 대단해 보이는 이유는 단순하다. n², n³, 심지어 n¹⁰⁰도 모두 P 안에 있다. 학부생이 보기에 n¹⁰⁰은 끔찍해 보이지만, 이 코스의 관점에서는 “문제는 풀렸다”의 카테고리에 들어간다. 다항식 시간이 곧 “합리적”이라는 약속은 다소 과감하지만, 후술하듯 모델 변경에 강건한(robust) 정의이기 때문에 경계선으로 채택된다.

4. 단일 테이프와 다중 테이프 — 시간의 환율

여기서 자연스러운 의심이 든다. 다중 테이프 TM은 단일 테이프보다 일을 훨씬 효율적으로 한다. 그러면 P의 정의가 모델 선택에 휘둘리는 것 아닌가?

핵심 결과: 다중 테이프에서 다항 시간이면, 단일 테이프에서도 다항 시간이다(차수만 두 배 정도 커진다). 그래서 P의 정의는 테이프 개수에 무관하다. P는 모델의 미세한 차이에 흔들리지 않는, 묵직한 클래스다.

5. 다항식 동치성 — 어떤 모델이든 P는 P

이 강건함은 단지 테이프 개수에 그치지 않는다. 합리적인 모든 결정적 계산 모델은 서로 다항식 시간 동치(polynomial-time equivalent)이다. 즉 한 모델에서 t(n) 시간에 풀리면, 다른 모델에서 t(n)^c 시간 안에 풀린다(c는 상수).

대표적인 합리적 모델들:

• 다중 테이프 TM — 단일 테이프와 다항식 동치 (위 정리).
• RAM(랜덤 접근 기계) — C 언어 비슷한 모델. TM과 다항식 동치이며, 이 덕분에 “알고리즘 책의 의사 코드”와 “TM 정의”가 같은 P를 묘사한다.
• 람다 계산(λ-calculus) — 함수 언어의 수학적 토대. 여전히 다항식 동치(단, 평가 전략에 따라 자세한 차수는 달라진다).
• 2차원 테이프 TM, 셔블 TM, 큐 기계 — 모두 다항식 동치.

이 동치성은 표면적으로는 코딩 연습처럼 보이지만, 그 결과는 묵직하다. 다항식 시간이라는 개념은 모델에 의존하지 않는 수학적 대상이다. 양자 모델까지 포함하면 이야기가 달라지지만, 고전 결정적 모델 안에서는 이 동치성이 P를 진정한 “자연 클래스”로 만든다.

6. P 안에 사는 친구들

구체적인 예를 셋 보자. 모두 P에 속함을 알고리즘으로 보인다.

세 예의 공통점은 단순하다. 알고리즘이 입력 크기에 대해 다항 차수 안에 끝나면 P. 우리가 “알고리즘”이라고 부를 때 흔히 떠올리는 것이 사실 P를 슬쩍 가리키고 있던 셈이다.

7. P는 “합리적 시간 안에 풀리는” 문제

실용적 명제(thesis)로서, P는 다음과 같이 받아들여진다.

이 명제는 정리가 아니다. n¹⁰⁰은 다항식이지만 현실적이지 않고, 1.0001ⁿ은 지수지만 작은 입력에서는 빠르다. 그럼에도 이 등식이 50년 넘게 살아남은 데는 두 가지 이유가 있다. 첫째, P 안의 자연 문제들은 거의 예외 없이 작은 차수의 다항식 알고리즘을 가진다 — n¹⁰⁰는 인공적이다. 둘째, P 바깥인 문제들은 반대로 비현실적인 시간을 요구하는 경우가 압도적이다. 경계선의 좌우는 실제로 잘 갈라져 있다.

그래서 우리는 다음 강의로 자연스레 넘어간다. P 바깥에 무엇이 있는가? 결정 가능하지만 다항 시간이 아닌 듯한 문제 — 만족 가능성, 클리크, 해밀턴 경로 — 가 줄지어 등장한다. 이들을 묶는 클래스가 NP이며, NP의 본성을 묻는 P = NP? 질문이 다음 강의의 무대를 연다.

1. 다시, 답을 ‘검증’한다는 것

주어진 부울 식 ϕ에 대해 “ϕ는 만족 가능한가?”를 물으면 직관적으로 어렵다. 변수 n개라면 2ⁿ가지 대입을 다 시험해 보는 게 가장 단순한 방법이고, 더 영리한 방법이 있는지는 — 솔직히 말해 — 아무도 모른다. 그러나 누군가가 “이 변수 대입이 ϕ를 만족시킨다”고 알려준다면 우리는 그 주장을 빠르게 확인할 수 있다. ϕ에 대입을 꽂고 평가하면 끝이다.

이 비대칭이 NP의 본질이다. NP는 답을 찾는 클래스가 아니라 답을 검증하는 클래스다.

2. NP의 두 정의

NP는 두 가지 방식으로 정의된다. 다행히 둘은 동치다.

이후로 그냥 NP라고 부른다. 핵심은 표어처럼 적힌다. NP = 다항 길이의 증명서가 존재하면 다항 시간에 검증할 수 있는 문제들.

3. NP 거주민들 — 인증서를 보면 안다

다음 문제들이 NP에 속함을 일일이 인증서로 확인하자. 각 인증서는 직관적이다.

일곱 문제 모두 검증은 누가 봐도 다항 시간이다. 그러나 답을 찾는 다항 알고리즘은 — 50년 동안 — 아무도 발견하지 못했다.

4. P ⊆ NP, 그리고 천만 달러

P에 속하는 언어 A에 대해, 검증기 V는 인증서를 무시하고 그냥 결정 알고리즘을 돌리면 된다. 즉 P ⊆ NP는 자명하다.

그렇다면 반대 방향, NP ⊆ P? 풀어 쓰면 “답을 빠르게 검증할 수 있다면 답도 빠르게 찾을 수 있는가?” 이것이 P 대 NP 문제이고, 클레이 수학 연구소의 밀레니엄 문제 일곱 중 하나로 백만 달러가 걸려 있다. 대다수 컴퓨터 과학자는 P ≠ NP를 믿는다. 그 이유는 이론적이라기보다 경험적이다 — 수십 년간 수만 명이 NP의 자연 문제 수천 개에 다항 알고리즘을 못 찾았으니까.

5. 다항 시간 매핑 환원

NP 안에서 어떤 문제가 다른 문제보다 “적어도 같은 만큼 어렵다”는 것을 어떻게 표현하나? 답은 환원(reduction)이다. 결정 가능성의 환원은 사상 환원(mapping reduction)이었는데, 여기서는 그 환원이 다항 시간 안에 계산되어야 한다.

대우를 취하면 더 유용한 형태가 된다. A ≤_p B 이고 A ∉ P 이면 B ∉ P. 즉 환원은 어려움을 “옮긴다” — 쉬운 문제로 줄어드는 어려운 문제는 사실 어렵지 않았다는 모순이 생기므로, 어려움이 환원의 목표 쪽으로 흘러간다.

같은 논리는 NP에도 적용된다 — A ≤_p B이고 B ∈ NP이면 A ∈ NP. 환원은 P, NP 모두를 보존한다.

6. 환원 실전: 3SAT ≤_p CLIQUE

이론은 충분하니 사례 하나를 구체적으로. 3SAT 인스턴스를 CLIQUE 인스턴스로 다항 시간 안에 변환할 수 있고, 변환 결과의 답이 곧 원본의 답이 되는 사상을 만들겠다.

이 환원의 매력은 단순함이다 — 절 → 그룹, 모순 없음 → 간선, 만족 가능성 → 클리크. 어려움이 옷만 갈아입었을 뿐 사라지지 않았다는 사실을, 그래프라는 옷에 비추어 다시 본 셈이다.

그렇다면 자연스러운 질문. 어떤 NP 문제든 SAT로 환원할 수 있는가? 그리고 SAT에서 출발해 다른 모든 NP 문제로도 환원할 수 있는가? 이 질문의 답이 “그렇다”라면, 단 하나의 문제만 P에 들어가도 NP 전체가 P에 빨려 들어간다. 이 경계선상의 문제들이 NP-완전이고, 다음 강의의 주인공이다.

1. NP-난해와 NP-완전

지난 강의에서 우리는 다항 시간 환원 ≤_p를 정의했다. 이 환원은 어려움을 화살표 방향으로 흘려보낸다 — A ≤_p B는 “B가 적어도 A만큼 어렵다”는 뜻이다. 이 흐름의 종착점에 서 있는 문제들이 있다.

NP-완전 문제는 NP의 “꼭대기”에 박힌 못이다. NP 안에 있으면서도 NP의 어떤 문제든 자기 위로 환원받는다. 비유하자면, 한 클래스의 학생들 중 모든 시험 범위를 자기 머릿속에 다 들고 있는 학생이다 — 다른 누구의 시험 답안도 자기를 통해 풀린다.

2. 한 문제가 무너지면 모두가 무너진다

이 정리는 NP-완전 문제가 가지는 무게를 한마디로 요약한다. SAT, CLIQUE, HAMPATH 중 어느 하나라도 다항 알고리즘이 발견되면 우리가 아는 “어려운” 문제 수천 개가 한꺼번에 풀린다. 반대로 NP-완전 문제 하나에 대해 다항 시간 하한이 증명된다면 P ≠ NP가 풀린다. 천만 달러는 이 단 하나의 문턱에 걸려 있다.

3. 환원의 동물원

NP-완전 문제 하나가 일단 박히면, 거기서 다른 문제로 환원시키는 것만으로 새로운 NP-완전 문제가 줄지어 등장한다. 다섯 가지 대표 환원을 둘러본다. 모든 환원은 다항 시간이다.

3.1 3SAT ≤_p CLIQUE — 절을 그룹으로

지난 강의의 복습. 3CNF 식 ϕ에서 절 k개에 대해 그래프 G를 만든다. 각 절의 세 리터럴 자리 하나하나가 정점이 된다. 같은 절의 정점끼리는 간선을 두지 않고, 서로 다른 절의 정점 사이에는 두 리터럴이 모순(예: x와 ¬x)이 아닐 때만 간선을 둔다. ϕ가 만족 가능 ⟺ G에 k-클리크 존재. 만족시키는 대입이 절마다 한 리터럴을 참으로 만들고, 그 리터럴 정점들이 일관성 덕에 모두 연결되어 클리크가 된다.

3.2 CLIQUE ≤_p VERTEX-COVER — 보색의 마술

입력 ⟨G, k⟩를 ⟨G̅, n − k⟩로 보낸다. 여기서 G̅는 G의 보색 그래프(같은 정점 집합, G에서 간선이 아니던 쌍이 G̅의 간선)이고 n = |V|.

한 줄짜리 마술처럼 보이지만, 그 안에는 “덮지 못함”과 “이웃 아님”이 보색에서 정확히 맞물린다는 조합론적 사실이 들어 있다.

3.3 3SAT ≤_p HAMPATH — 다이아몬드와 절 노드

이 환원은 가장 정교하다. 3CNF 식 ϕ가 변수 x₁, …, x_n과 절 c₁, …, c_m를 가진다고 하자. 그래프 G는 변수마다 “다이아몬드(diamond)”라 부르는 사다리 모양 가젯을 두고, 절마다 절 노드(clause node) 하나를 둔다.

3.4 HAMPATH ≤_p UHAMPATH — 방향을 무방향으로

UHAMPATH는 무방향 그래프에서의 해밀턴 경로 문제다. 방향 그래프 G의 각 정점 v를 세 정점 v_in, v_mid, v_out으로 분해해 무방향 그래프 G′를 만든다.

“in / mid / out” 분해는 무방향성에서 사라진 방향 정보를 토폴로지로 살려내는 영리한 트릭이다. v_mid는 양옆을 한 번씩만 사용해야 하므로 사실상 화살표 역할을 한다.

3.5 3SAT ≤_p SUBSET-SUM — 자릿수의 분리 마술

SUBSET-SUM의 NP-완전성은 부울 논리에서 산수로의 점프라 특히 인상적이다. 3CNF 식 ϕ에 변수 n개, 절 m개가 있다고 하자. (n + m)자리 십진수들의 집합을 만들어 합 목표 t를 정한다.

자릿수가 곧 채널이다 — 변수와 절을 서로 다른 자릿수에 가두어 두면, 자릿올림 없는 산술이 곧 부울 논리의 진리값 책정과 절 만족 검사를 동시에 수행한다. 부울에서 산수로의 다리이자, NP-완전성이 얼마나 침투력 강한지를 보여주는 사례다.

4. 동물원이 폭발적으로 자라는 이유

NP-완전 문제는 카프(R. Karp)의 1972년 목록에서 출발해 21세기에는 수만 개에 이른다. 왜 이렇게 빠르게 늘어나는가? 이유는 환원의 추이성(transitivity)이다.

증명은 두 다항 환원 함수의 합성이 다시 다항이라는 사실에서 곧장 따라온다. 결과적으로 어떤 새 문제 X가 NP에 속하고 NP-완전이라 알려진 문제 B에 대해 B ≤_p X라는 환원만 보이면, X 또한 NP-완전이다 — 임의의 A ∈ NP에 대해 A ≤_p B ≤_p X이기 때문이다.

그래서 SAT 하나가 NP-완전이라고 증명된 다음(쿡-레빈 정리, 다음 강의), 그로부터 3SAT, CLIQUE, VERTEX-COVER, INDEPENDENT-SET, HAMPATH, UHAMPATH, SUBSET-SUM, KNAPSACK, GRAPH-COLORING, SET-COVER, BIN-PACKING, … 줄줄이 사탕이 풀린다. 첫 번째 도미노만 쓰러뜨리면 나머지는 거저였다.

5. 다음으로 — 첫 번째 도미노

지금까지 우리는 NP-완전 문제 하나만 손에 들어오면 환원으로 무한정 늘릴 수 있다는 사실을 보였다. 그러나 “첫 번째” NP-완전 문제는 어떻게 만들어졌는가? 그것은 환원의 사슬을 출발시킬 단단한 첫 발걸음이어야 한다.

1971년 스티븐 쿡(Stephen Cook), 그리고 거의 동시에 레오니드 레빈(Leonid Levin)이 같은 결과를 독립적으로 증명했다. SAT은 NP-완전이다. 즉, NP에 속한 임의의 언어가 SAT으로 다항 시간에 환원된다. 이 정리는 NP에 속한 언어의 정의 — 다항 시간 비결정 TM이 수락한다는 것 — 자체를 부울 식으로 “인코딩”함으로써 증명된다.

다음 강의는 이 인코딩의 디테일을 다룬다. 비결정 TM의 계산을 일종의 표(tableau)로 그리고, 그 표가 “수락하는 합법적 계산”이라는 사실을 한 줄짜리 거대한 부울 식으로 옮겨 적는 작업. 그것이 바로 NP-완전성 이론 전체의 첫 도미노다.

1. 출발점: 왜 하필 SAT인가

NP-완전성이라는 개념을 처음 정의했을 때 한 가지 의문이 따라붙는다. NP-완전 문제가 정말 존재하긴 하는가? 정의상 그것은 NP에 속하면서, NP의 모든 문제가 자기 자신으로 다항 시간 환원되는 거대한 자석 같은 문제다. 누군가가 그 자석을 한 번이라도 만들어 보여 주지 않는다면, 클래스의 정의는 공허할 수도 있다.

1971년 스티븐 쿡과 1973년 레오니드 레빈이 독립적으로 이 자석을 직접 손에 쥐여 주었다. 그 자석의 이름이 바로 SAT(boolean satisfiability problem, 부울식 충족성 문제)이다. SAT는 변수들의 논리식이 주어졌을 때 그 식을 참으로 만드는 할당이 존재하는지를 묻는 결정 문제다. 결과는 충격적으로 단순하면서도 깊다.

(1)은 거의 자명하다. 식 φ가 주어지고 누군가 만족 할당 τ를 인증서로 건네주면, τ를 φ에 대입해 결과가 참인지 다항 시간에 확인하면 된다. 검증자는 한 줄 평가기 그 이상도 이하도 아니다. 흥미로운 부분은 (2)다. 임의의 NP 언어 A를 SAT로 환원해야 한다 — 그것도 A의 정의에 대해 거의 아무것도 모르는 채로 말이다.

2. 환원의 골격: 계산 이력을 식으로

A가 NP 언어라 하자. 정의에 의해 A를 결정하는 비결정적 튜링 기계(NTM) N과 다항식 t(n)이 존재해서, 입력 w(길이 n)에 대해 N은 t(n) 단계 안에 어떤 비결정 분기를 따라 수락 여부를 끝낸다. 우리가 만들 환원은 다음 한 줄로 요약된다.

다시 말해 φ_w의 만족 할당이란 곧 "N이 w를 어떻게 받아들이는가"의 청사진이다. 변수는 청사진의 각 칸이고, 절(clause)은 그 청사진이 진짜 N의 동작 규칙을 따르는 합법적 이력임을 강제한다.

3. 표(tableau) 그리기

이제 실제로 청사진의 종이를 펼쳐 보자. 입력 길이가 n일 때 t(n)을 그저 t로 줄여 적는다. 우리는 가로 t칸, 세로 t칸짜리 격자(tableau)를 그린다. 행 인덱스 i는 시간(0행이 초기, t-1행이 종료), 열 인덱스 j는 테이프 위치다. 각 칸 ⟨i, j⟩에 들어갈 내용은 다음 두 가지 중 하나다.

• 테이프 기호 s ∈ Γ — 그 시각 그 위치의 글자
• (상태, 기호) 쌍 — 헤드가 그 위치에 있고 상태가 q일 때, 칸에는 ⟨q, s⟩처럼 합쳐 쓴다

한 행을 좌에서 우로 읽으면 한 시각의 전체 구성(configuration)이 된다. 행이 하나씩 아래로 내려간다는 것은 N이 한 단계 움직였다는 뜻이다.

              j=0   j=1   j=2   j=3   ...   j=t-1
       i=0 |  q0,w1 | w2  | w3  | ⊔   | ... | ⊔   |   초기 구성
       i=1 |  w1   | q', w2 | w3 | ⊔   | ... | ⊔   |   한 칸 우측 이동, 상태 q'
       i=2 |  w1   | w2'  | q'',w3 | ⊔ | ... | ⊔   |
        .
        .
       i=t-1| ... 어딘가에 q_accept 등장 ...        |
    

이 격자가 합법적인 수락 이력이라는 사실을 부울식으로 옮기는 데 필요한 변수와 절은 다음과 같다.

4. 네 종류의 절

이제 우리는 변수들의 진리값이 진짜 격자를 묘사하도록 강제하는 절들을 적는다. 이를 네 그룹으로 나누어 부른다 — cell, start, accept, move.

4.1 cell — 각 칸은 정확히 한 글자

먼저 각 칸이 적어도 하나의 내용은 가지고, 그러나 두 가지를 동시에 가지지 않게 만들어야 한다. 칸 ⟨i, j⟩에 대해

  ( ⋁s ∈ C xi,j,s )   ∧   ( ⋀s ≠ t ¬xi,j,s ∨ ¬xi,j,t )
    

전자는 "무엇이든 적혀 있다", 후자는 "두 글자가 동시에 적혀 있을 수는 없다"는 뜻이다. 칸이 t²개이고 각 칸의 절 길이는 |C|에 의해 정해지므로, 이 그룹의 총 절 개수는 O(t²)이다.

4.2 start — 0행은 초기 구성

입력 w = w₁ w₂ … w_n이 주어졌을 때, 0행은 정확히 다음 모양이어야 한다.

  x0, 0, ⟨q0, w1⟩  ∧  x0, 1, w2  ∧  …  ∧  x0, n-1, wn  ∧  x0, n, ⊔  ∧  …  ∧  x0, t-1, ⊔
    

(한 줄짜리 합접이라 절 하나로 표현하기 어색해 보이면, 각 합접 항을 단일 리터럴 절로 따로따로 두면 된다.) 이 그룹의 절 개수는 O(t)이다.

4.3 accept — 어딘가에 수락 상태가 등장

N이 w를 수락한다는 사실은 이력 어딘가에 수락 상태 q_accept가 등장했다는 뜻이다. 격자의 어느 칸이든 좋다.

  ⋁i, j, s ∈ Γ  xi, j, ⟨qaccept, s⟩
    

거대한 OR 절 하나로 충분하며 길이는 O(t²)이다. (전이 후 정지하는 NTM이라 가정하면 헤드가 일단 q_accept에 도달하면 그 자리에 머무는 식으로 다듬을 수 있다.)

4.4 move — 인접 행 사이는 N의 전이 함수와 일치

가장 중요한 그룹이다. 1행, 2행, …, (t-1)행이 정말 0행에서 N의 규칙에 따라 한 단계씩 진행된 결과여야 한다. 한 번의 NTM 단계는 헤드와 그 좌우 한 칸씩, 총 세 칸의 내용에만 의존하므로 우리는 격자 전체를 한꺼번에 보지 않아도 된다.

대신 격자 위의 모든 2행 × 3열 윈도우를 살펴 그 윈도우가 N에서 합법적인지를 묻는다. 2 × 3 윈도우란 행 ⟨i, i+1⟩과 열 ⟨j-1, j, j+1⟩이 만나 만드는 작은 사각형이다.

            j-1   j     j+1
       i  | a  |  b  |  c  |
      i+1 | a' |  b' |  c' |
    

"합법적 윈도우"란, 만약 i행의 (a, b, c)가 N의 어떤 한 단계로 (a′, b′, c′)이 될 수 있다면 통과, 아니면 부적합이다. 합법적 윈도우의 집합은 N의 전이 함수 δ로부터 미리 유한하게 계산해 둘 수 있다 — N에 의존할 뿐 입력 w와는 무관하다.

이제 각 윈도우 위치 ⟨i, j⟩에 대해 다음 절을 둔다.

  ⋁(a,b,c,a',b',c') ∈ 합법윈도우  ( xi,j-1,a ∧ xi,j,b ∧ xi,j+1,c ∧ xi+1,j-1,a' ∧ xi+1,j,b' ∧ xi+1,j+1,c' )
    

(이 거대한 OR-of-AND를 CNF로 옮길 때는 분배 법칙을 쓰거나, 보조 변수를 도입해 부피를 다항으로 유지한다. 길이가 N에만 의존하는 상수 크기의 OR이므로 어느 쪽이든 다항 시간에 끝낸다.) 윈도우 개수는 O(t²)이다.

네 그룹을 모두 합접으로 묶으면 우리의 부울식 φ_w가 완성된다.

  φw  =  φcell  ∧  φstart  ∧  φaccept  ∧  φmove
    

5. 환원의 정확성과 다항성

다항성도 따져 보자. 변수 개수는 O(t²), 절 개수는 cell·start·accept·move 모두 합쳐 O(t²)에 N에 의존하는 상수가 곱해진 정도다. φ_w를 종이에 적는 일은 입력 w를 훑으며 격자 좌표를 따라 출력하는 것이라 다항 시간에 끝난다. 따라서 환원 자체가 다항 시간에 가능하다 — A ≤_p SAT.

6. 3SAT까지 — 절을 셋으로 자르기

SAT의 절은 임의 길이를 허용하지만, 실전에서는 한 절의 리터럴 수가 정확히 셋인 3SAT이 환원의 표준 출발점이 되는 일이 많다. 다행히 SAT가 NP-완전이라는 사실로부터 3SAT가 NP-완전임을 잇는 다리는 짧다.

   (l1 ∨ l2 ∨ z1)  ∧  (¬z1 ∨ l3 ∨ z2)  ∧  …  ∧  (¬zk-3 ∨ lk-1 ∨ lk)
      

변환 후 절 개수는 원본의 합 길이에 비례해 다항이다. 따라서 SAT ≤_p 3SAT, 그리고 임의 NP 언어 A는 A ≤_p SAT ≤_p 3SAT.

7. 이 정리가 우리에게 주는 것

쿡-레빈 정리의 진짜 가치는 그 자체보다 그것이 열어 주는 통로에 있다. 새로운 결정 문제 B의 NP-완전성을 보이고 싶다고 하자. 정의에 따르면 모든 NP 언어가 B로 환원됨을 보여야 하는데, 이는 매번 NTM의 격자를 들고 와 사투를 벌이라는 뜻이다. 그러나 SAT 또는 3SAT가 NP-완전이라는 사실을 손에 쥐고 있으면, 우리는 한 가지만 보이면 된다.

이로써 이후의 모든 NP-완전성 증명은 "어디서 출발할까" 하는 카탈로그 게임이 된다. 첫 번째 NP-완전 문제를 정직하게 만들어 둔 쿡과 레빈의 수고가 그 카탈로그의 맨 윗 줄을 지탱하고 있는 셈이다.

다음 강의에서는 시간에서 공간으로 무대를 옮긴다. 메모리만 다항이면 시간이 지수여도 괜찮다는 클래스 PSPACE를 정의하고, 비결정적 공간이 결정적 공간과 본질적으로 다르지 않다는 사비치(Savitch) 정리를 만난다 — 시간 영역의 P 대 NP 문제가 공간에서는 한 변의 제곱 차이로 깔끔하게 해결되는, 약간 짓궂은 광경이 펼쳐진다.

1. 자원의 축을 바꾸기

시간 복잡도에서 우리는 "단계 수"를 자원으로 셌다. 그러나 컴퓨터의 한계가 시간만은 아니다. 어떤 알고리즘은 빠르게 끝나지만 메모리를 게걸스럽게 먹어 치우고, 또 어떤 알고리즘은 느리지만 작은 노트만으로도 충분하다. 이번 강의에서는 자원의 축을 메모리로 바꾸어 본다.

여기서 한 가지 약속이 필요하다. 메모리를 측정한다고 해서 입력 w 자체를 다시 셀 수는 없다 — 입력만으로 이미 n 비트가 든다. 우리가 진짜 관심 있는 것은 기계가 추가로 끼적이는 노트의 양이다. 그래서 공간 복잡도용 튜링 기계는 보통 입력 테이프(읽기 전용)와 작업 테이프(읽기/쓰기)를 분리한 모델을 사용한다.

입력 자체는 셈에서 빠지므로 SPACE(log n)처럼 입력보다 작은 공간 클래스를 정의하는 일도 가능하다. 본 강의에서는 다항 공간만 다루지만, 그런 정의의 미세함이 가능한 까닭은 이 분리된 모델 덕분이라는 점을 머리 한구석에 둬두자.

2. 시간과 공간 사이의 격자

두 자원은 서로를 묶는 두 가지 자명한 부등식을 가진다. 첫 번째는 거의 정의에 가깝다.

두 번째는 약간의 사색을 요구한다. 공간을 적게 쓰는 기계가 시간을 얼마까지 쓸 수 있는가? 답은 "의외로 많지만 그 한계가 깔끔하다"이다.

두 관찰을 묶으면 다음 다이어그램이 자연스럽다.

   P  ⊆  NP  ⊆  PSPACE  ⊆  EXPTIME
    

맨 왼쪽은 자명, 두 번째는 NP의 다항 검증자가 인증서와 함께 다항 시간에 굴러가니 다항 공간만 쓴다는 데서 나온다 — 또는 모든 가능 인증서를 한 통의 다항 길이 변수에 저장하면서 차례로 시도해도 다항 공간이 충분하다. 마지막 PSPACE ⊆ EXPTIME은 관찰 2의 직접 따름이다.

흥미로운 점은 이 사슬 어디에서도 진짜 분리가 알려져 있지 않다는 것이다. P ≠ PSPACE인지, NP ≠ PSPACE인지, 어느 쪽도 풀리지 않은 채 책상 위에 놓여 있다.

3. PSPACE의 대표 시민: TQBF

NP에 SAT가 있다면 PSPACE에는 그 양화 버전이 있다. SAT는 "어떤 할당이 식을 만족시키는가"를 묻지만, 진짜 게임은 변수마다 ∀와 ∃가 번갈아 붙을 때 시작된다.

  φ = Q1 x1  Q2 x2  …  Qk xk  ψ(x1, …, xk)
      

TQBF가 PSPACE에 속한다는 사실을 보이는 자연스러운 방법은 양화자 한 개씩을 손으로 까보는 재귀이다.

실은 TQBF는 PSPACE-완전이다 — 그 사실의 증명은 쿡-레빈의 변형이지만 이 강의의 메인 메뉴는 따로 있다.

4. 사비치 정리 — 비결정성을 공간에서 메우다

시간 영역에서 P와 NP의 차이가 얼마나 큰지는 아무도 모른다. 그런데 공간 영역에서는 사정이 다르다. 1970년 월터 사비치가 "비결정 공간을 결정 공간으로 옮길 때 잃는 것은 한 변을 제곱할 만큼뿐"임을 보였다.

증명의 무대는 임의의 NTM N과 그 안에서 일어나는 구성 그래프(configuration graph)다. 입력 w가 주어졌을 때 N의 구성은 (상태, 작업 테이프 내용, 두 헤드 위치)로, 작업 공간이 s 칸이면 가능한 구성은 2^O(s)개. N이 w를 수락한다는 것은 시작 구성 c_start에서 어떤 수락 구성 c_accept로 이르는 경로가 N의 한 단계 관계 안에서 존재한다는 뜻이다.

핵심은 "도달 가능성"을 분할 정복으로 풀어내는 다음 술어다.

CANYIELD는 다음 재귀로 계산된다.

  CANYIELD(c1, c2, t):
    if t = 1 :  return ( c1 = c2  또는  c1 ⊢ c2 in N )
    for each 가능한 중간 구성 m :
      if CANYIELD(c1, m, ⌈t/2⌉)  AND  CANYIELD(m, c2, ⌊t/2⌋) :
        return YES
    return NO
    

핵심 트릭은 두 재귀 호출을 차례로 하고 그 사이에 작업 공간을 재활용하는 것이다 — 깊이는 단지 log₂ t에 비례하고, 한 레벨이 차지하는 변수는 c₁, c₂, m의 세 구성이다. 각 구성은 s 칸을 차지하므로 한 레벨당 O(s) 공간.

  O(s) × O(s) = O(s2).
      

주목할 만한 점 두 가지. 첫째, 시간으로 같은 일을 시도했다면 결과는 끔찍했을 것이다 — 우리는 t를 t/2씩 쪼개도 두 호출 모두를 수행하므로 시간상 곱이 절약되지 않는다. 그러나 공간은 재사용 가능한 자원이라 이 분할 정복이 의미를 갖는다. 둘째, 우리가 다룬 t가 2^O(s)이라 깊이가 O(s)였다는 점이다. 시간으로 설정한 t였다면 깊이가 너무 작아 별 도움이 안 됐을 것이다.

이 결과를 시간 영역의 미해결 문제 P =? NP와 비교해 보면 약간의 위안과 동시에 약간의 좌절감을 느끼게 된다. 메모리 자원에서는 결정성과 비결정성이 한 변을 제곱하는 일로 거리가 메워진다 — 그런데 시간에서는 그조차도 우리가 모른다.

5. 정리하며, 그리고 다음 강의

오늘의 수확을 헤아려 두자. 공간 클래스 SPACE(s)와 NSPACE(s)를 입력 테이프와 작업 테이프를 분리한 모델 위에서 정의하고, 그 정의로부터 PSPACE와 NPSPACE를 얻었다. 시간/공간의 두 자명한 부등식은 P ⊆ NP ⊆ PSPACE ⊆ EXPTIME이라는 사슬을 빚어냈고, 이 사슬 어느 곳에서도 진짜 진부분 관계가 알려져 있지 않다는 사실을 확인했다.

그 다음 PSPACE의 대표적 시민 TQBF를 만났다. 이 문제는 양화자 게임에서 ∃ 측의 필승 여부를 묻는 것과 다름없고, 양화자 한 겹씩 까는 재귀로 다항 공간에 결정 가능했다. 마지막으로 사비치 정리는 도달 가능성을 분할 정복으로 다루어, 비결정 공간 s를 결정 공간 s²로 시뮬레이션할 수 있음을 보였다 — 결과적으로 PSPACE = NPSPACE.

다음 강의에서는 이 PSPACE 안에서 가장 어려운 자리에 앉은 문제들 — PSPACE-완전 문제들 — 의 모습을 본격적으로 들여다본다. TQBF가 그 자리의 첫 거주민이고, 그로부터 환원되는 게임 이론적 결정 문제들이 줄을 잇는다. 시간이 흘러도 메모리는 잊지 않는다는 사실을 가장 적나라하게 보여 주는 클래스가 PSPACE다.

1. 한 클래스의 "최악"을 잡는 법

NP에서 SAT가 차지했던 위치를 떠올려 보자. SAT 하나만 잘 풀면 NP 전체가 무너지는, 그런 압도적 위치 말이다. PSPACE에서도 똑같은 그림을 그릴 수 있다. 다만 자원이 시간이 아니라 공간이라는 점만 다를 뿐이다. 이번 강의의 주연은 TQBF(True Quantified Boolean Formula, 참인 양화 부울식)이고, 조연은 Savitch 정리에서 이미 한 번 만난 재귀적 분할이다.

왜 환원의 척도로 "다항 시간"을 쓰는가? PSPACE라는 더 큰 그릇 안에서 의미 있는 비교를 하려면, 환원 자체는 비교 대상보다 훨씬 약한 자원으로 묶어 두어야 한다. 시간 다항이면 공간도 다항이므로, 다항 시간 환원은 PSPACE 내부의 구조를 충분히 보존한다.

다시 말해, PSPACE-완전 문제 한 마리만 효율적으로 잡아도 다항 시간으로 다항 공간 전체를 정복하는 셈이다. 그래서 PSPACE-완전성은 단순히 어렵다는 라벨이 아니라, "이 한 점이 무너지면 클래스 전체가 무너진다"는 절단점의 의미를 갖는다.

2. TQBF: 양화의 풀스택

SAT가 ∃만 쓰는 양화식의 진리 판정이라면, TQBF는 ∃와 ∀가 자유롭게 교차한다. 양화자가 한 번 더 끼어들 때마다 "결정 한 단계"가 더해지고, 게임으로 치면 수가 한 번 더 두어지는 셈이다.

증명은 두 부분으로 나뉜다. 한 쪽은 쉬운 멤버십, 다른 한 쪽은 핵심 어려움이다.

3. TQBF ∈ PSPACE

먼저 멤버십. 입력 φ = Q₁x₁ … Q_nx_n ψ를 받았다고 하자. 재귀적으로 평가한다. φ의 가장 바깥 양화자가 ∃x₁이면 x₁ = 0과 x₁ = 1을 차례로 시도해 둘 중 하나라도 참이면 참을 반환한다. ∀x₁이면 둘 다 참이어야 참을 반환한다. 양화자가 모두 사라지면 ψ를 직접 계산한다.

재귀 깊이는 양화자의 개수 n이고, 각 단계에서 부분 식의 사본 대신 변수 할당만 기억하면 된다. 따라서 공간 사용량은 O(n + |φ|), 즉 n의 다항이다. 이 단순한 깊이 우선 평가만으로 TQBF ∈ PSPACE.

4. PSPACE-경도: 식이 너무 커지면 안 된다

이제 어려운 방향이다. 임의의 A ∈ PSPACE를 받아, A ≤_p TQBF임을 보여야 한다. PSPACE TM M이 입력 w에서 공간 s = n^k를 쓴다고 하자(여기서 n = |w|). 우리의 임무는 다항 시간에 양화 부울식 φ_M,w를 구성해 다음을 만족시키는 것이다.

φ_M,w가 참 ⇔ M이 w를 받아들임.

자연스러운 시도, 그리고 그 좌절

M의 형태(configuration)는 길이 O(s) = O(n^k) 비트로 인코딩된다. Cook–Levin 식 발상으로, 시작 형태 c_start에서 받아들임 형태 c_accept까지의 형태 수열을 통째로 변수화하면? M의 실행 시간은 최대 2^O(s)이다(공간 한계 TM의 정지성을 위해). 형태 수열은 그러므로 길이 2^O(s), 변수 개수도 2^O(s). 식 크기가 지수가 되어 다항 시간 환원이 깨진다. 단순 인코딩은 실패한다.

Savitch 스타일 재귀적 분할

해법은 시간이 아니라 중간점을 양화로 잡아내는 것이다. 두 형태 c₁, c₂와 단계 수 t에 대해, "c₁에서 c₂로 ≤ t 단계에 갈 수 있다"를 표현하는 식 φ_c1,c2,t를 재귀적으로 만든다.

기저 t = 1: φ_c1,c2,1은 c₁ = c₂이거나 c₁이 한 단계로 c₂에 가는지 확인하는, Cook–Levin식 국소 검증 식. 크기는 O(s).

재귀 단계: 직관적으로는

∃m [ φ_c1,m,t/2 ∧ φ_m,c2,t/2 ]

이라고 쓰고 싶지만, 이 형태는 재귀가 한 단계 내려갈 때마다 식이 두 배가 된다. 깊이 log T = O(s)이므로 결국 다시 지수 폭발이다.

핵심 트릭은 ∀를 이용해 두 부분 식을 같은 식 하나로 합치는 것이다.

φ_c1,c2,t ≡ ∃m ∀(a,b) ∈ {(c₁,m), (m,c₂)} φ_a,b,t/2.

여기서 ∀(a,b) ∈ {…}는 두 가지 형태 쌍에 대한 양화이며, 새 변수 (a,b)를 도입한 뒤 "(a,b)가 (c₁,m) 또는 (m,c₂)이면 φ_a,b,t/2가 성립" 같은 함의로 풀어 쓴다. 이렇게 하면 재귀 호출이 식 안에 두 번 등장하는 대신 한 번만 등장한다.

크기 분석

각 재귀 단계에서 식 크기는 다음 점화식을 만족한다.

L(t) = L(t/2) + O(s), L(1) = O(s).

풀면 L(T) = O(s · log T) = O(s²). 다항이다. 양화자의 깊이도 log T = O(s) = O(n^k)로 다항이다. 마지막으로

φ_M,w ≡ φ_{cstart, caccept, T}

로 두면 φ_M,w가 참 ⇔ M이 w를 받아들임. 환원 자체는 형태 인코딩과 재귀적 식 생성이 전부이므로 다항 시간에 끝난다. 따라서 TQBF는 PSPACE-완전이다. □

5. 클래스 사이의 풍경

이쯤에서 그림을 정리하자. 다음 포함 관계는 모두 알려진 사실이다.

P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ EXPSPACE.

등호는 Savitch 정리, NPSPACE ⊆ EXPTIME은 형태 그래프 크기가 2^poly임에서 곧바로 따른다. 이 사슬에서 어느 두 인접 클래스가 진짜로 같은지 다른지는 대부분 미해결이지만, 다음 강의에서 공부할 위계 정리는 P ⊊ EXPTIME과 PSPACE ⊊ EXPSPACE를 확정해 준다. 따라서 위 사슬에서 적어도 한 곳은 진짜 ⊊이다. 단지 어디인지를 모를 뿐.

6. 양화 게임으로서의 TQBF

마지막으로, TQBF를 게임이라는 다른 렌즈로 보자. φ = ∃x₁ ∀x₂ ∃x₃ … ψ를 두 플레이어의 대국으로 읽자. ∃ 차례에는 플레이어 E가 변수를 0/1로 둔다. ∀ 차례에는 플레이어 A가 둔다. 모든 변수가 결정되면 ψ를 평가한다. ψ가 참이면 E의 승리, 거짓이면 A의 승리.

그러면 φ가 참이라는 것은 정확히 E가 승리 전략을 갖는다는 뜻이다. 게임 트리의 minimax 평가가 곧 양화식의 재귀적 평가다. ∃는 max, ∀는 min, 잎은 ψ의 진리값. 다항 깊이의 minimax 트리 위에서 누가 이기는가 — 이 질문이 PSPACE의 가장 어려운 문제와 같은 난도라는 사실은, 다음 강의에서 일반화 지오그래피와 보드게임으로 곧장 이어진다.

1. 양화에서 게임으로

지난 강의에서 TQBF를 게임으로 읽는 법을 잠깐 보았다. ∃ 차례의 플레이어와 ∀ 차례의 플레이어가 번갈아 변수를 채우고, 마지막에 식이 참이면 ∃이 이긴다. 이 시점에서 합리적인 의문 하나. 그렇다면 우리가 일상에서 즐기는 보드게임 — 체스, 바둑, 오목 — 의 결정 문제들도 같은 틀에 들어가지 않을까?

답은 "들어간다"이지만, 어디에 들어가는지가 미묘하다. 보드 크기를 매개변수로 일반화하면 어떤 게임은 PSPACE-완전, 어떤 게임은 EXPTIME-완전이 된다. 이번 강의에서는 그 가운데 가장 깔끔한 견본인 일반화 지오그래피를 통해, "2인 완전정보 게임의 승자 판정 = 양화식의 진리 판정"이라는 등식을 또렷이 보일 것이다.

양화자의 깊이는 게임의 길이와 같다. 게임이 다항 길이로 끝나면 PSPACE 안에 머문다(TQBF의 PSPACE 멤버십과 같은 깊이 우선 평가). 게임이 지수적으로 길어질 수 있으면 EXPTIME 영역으로 올라간다.

2. 일반화 지오그래피

어릴 적 끝말잇기를 떠올려 보자. 한 사람이 단어를 말하면 다음 사람은 그 단어의 마지막 글자로 시작하는 단어를 댄다. 더 못 대는 쪽이 진다. 이 게임을 그래프로 추상화한 것이 지오그래피다. 정점은 단어, 간선은 "끝 글자가 시작 글자와 일치"라는 관계.

왜 토큰 한 개로, 왜 정점 재방문 금지인가? 단어 끝말잇기에서 같은 단어를 두 번 쓰지 않는 규칙을 그대로 옮긴 것이다. 이 단순한 규칙 두 줄이 게임을 충분히 풍부하게 만들어 준다.

멤버십 GG ∈ PSPACE는 어렵지 않다. 위치 = (현재 정점, 방문한 정점 집합)인데, 후자를 비트 벡터로 들고 있어도 |V| 비트면 충분하다. minimax를 깊이 우선으로 재귀 평가하면 재귀 깊이도 |V|. 따라서 다항 공간이면 충분하다.

핵심은 PSPACE-경도 — 즉 TQBF ≤_p GG. 임의의 양화 부울식 φ를 받아, 그래프 G_φ와 시작 정점을 만들어 "φ가 참 ⇔ 선공 승리"가 되도록 한다.

3. 환원 가젯

일반성 잃지 않고 φ를 다음과 같이 정규화하자. 양화자가 ∃와 ∀가 교대로 나오고, 행렬은 3-CNF.

φ = ∃x₁ ∀x₂ ∃x₃ … Q_nx_n C₁ ∧ C₂ ∧ … ∧ C_k.

그래프 G_φ는 두 부분으로 나뉜다. 변수 가젯의 사슬과, 그 끝에 매달린 절 가젯들.

변수 가젯: 다이아몬드

각 변수 x_i마다 다이아몬드 모양의 가젯을 둔다. 위쪽 정점 a_i에서 두 갈래(왼쪽: x_i = T, 오른쪽: x_i = F)로 갈라졌다가 아래쪽 정점 b_i에서 다시 합쳐진다. 그리고 b_i는 다음 변수의 a_i+1로 이어진다.

다이아몬드의 갈래는 두 개의 정점(t_i와 f_i)으로 표현된다. 시작 정점이 a_i이고 차례인 플레이어가 t_i 또는 f_i를 고르면, 상대편이 자동으로 다음 정점 b_i로 가야 한다. 이 한 라운드 안에서 차례인 플레이어가 사실상 변수의 진리값을 결정한다.

핵심은 차례를 어떻게 짜 두느냐. 양화자 ∃x_i이면 i번째 다이아몬드의 a_i가 플레이어 1(∃)의 차례에 오도록, ∀x_i이면 플레이어 2(∀)의 차례에 오도록 정렬한다. 다이아몬드 한 개는 두 수(a_i → t_i/f_i → b_i)를 잡아먹으므로, 시작 위치를 적절히 잡으면 차례가 정확히 맞아떨어진다.

마무리: 절 가젯과 함정

n번째 다이아몬드의 b_n은 절 선택 정점 c로 이어진다. c에서는 플레이어 2(∀)의 차례. ∀는 절 C₁, …, C_k 중 하나를 고른다. 즉 c에서 절 정점 v_j로 간선이 나와 있고, ∀는 그중 하나를 선택한다.

절 정점 v_j에서는 다시 플레이어 1(∃)의 차례. v_j는 자신의 절 C_j의 세 리터럴 각각으로 간선이 나 있다. ∃는 그중 하나를 골라 이동한다. 그리고 결정적인 부분: 각 리터럴 정점은, 변수 가젯에서 해당 리터럴을 "참"으로 만든 갈래의 정점(t_i 또는 f_i)으로 간선이 이어져 있다. 즉 리터럴 x_i는 t_i로, ¬x_i는 f_i로.

그런데 t_i 혹은 f_i는 이미 게임 초반에 한 번 방문되었을 수도, 그렇지 않을 수도 있다. 이게 트릭이다. 변수 단계에서 차례인 플레이어가 t_i를 고르면 t_i가 방문 표시된다. 즉 x_i를 T로 정한 셈. 그러면 절 단계에서 어떤 리터럴이 t_i로 가려 해도 정점이 이미 사용되었으므로 갈 수 없다.

잠깐, 방향이 거꾸로 아닌가? 다시 정리. 절 가젯에서 ∃이 리터럴 ℓ을 골라 t_i(또는 f_i)로 들어가면, 그 정점에서 다시 한 수가 나가야 한다. 그래프를 설계할 때, t_i와 f_i 각각에서 더 이상 갈 곳이 없도록(혹은 한 단계만 더 가는 막다른 길이도록) 만든다. 그러면 절 단계에서 ∃이 ℓ을 골라 들어가면 그 다음은 ∀의 차례인데 ∀는 갈 곳이 없어 진다 — 단, 그 정점 t_i/f_i가 아직 방문되지 않았을 때만. 만약 변수 단계에서 이미 방문되었다면 ∃이 그 리터럴 정점으로 들어가는 수 자체가 막혀, 결국 ∃의 막다른 길이 되어 ∃이 진다.

요약하자면, 절 단계에서 ∃이 살아남으려면 절 C_j를 만족시키는 리터럴이 적어도 하나는 있어야 하고, 그 리터럴에 해당하는 변수 정점이 방문되지 않은 상태여야 한다. 그런데 변수 가젯에서 t_i를 골랐다는 것은 x_i = T로 두었다는 뜻이고, 이때 방문되지 않은 채 남은 정점은 f_i다. f_i는 x_i = F를 의미하는 리터럴 ¬x_i의 표적이고, 따라서 ¬x_i가 절을 만족시키려면 절 안에 ¬x_i가 있어야 한다. 결국 "리터럴 ℓ이 절을 참으로 만든다"와 "ℓ에 대응하는 정점이 절 단계에서 비방문 상태이다"가 정확히 일치하도록 설계된다.

4. 보드게임의 자리는 어디인가

일반화 지오그래피의 환원 기술은, 더 본격적인 보드게임으로 확장된다. 다만 클래스 위치는 게임의 "자연스러운 길이"에 따라 달라진다.

다항 길이 게임은 PSPACE 안에 머문다. 위치 인코딩과 전략 평가가 다항 공간 안에 들어가기 때문이다. 지수 길이 게임은 EXPTIME으로 올라간다. 시간 자체가 지수가 되면 PSPACE 평가가 통하지 않는다.

• n×n 체스(50수 무승부 규칙 없이): 대국이 지수 길이일 수 있어 EXPTIME-완전.
• n×n 바둑(일본 룰 변종): 대국 길이가 지수, EXPTIME-완전. 단, 어떤 룰을 채택하느냐로 결과가 흔들린다.
• n×n 오목(Gomoku) 류의 라인업 게임: 보통 PSPACE-완전.
• Generalized Geography: 길이 ≤ |V|이므로 PSPACE-완전.

"무승부 규칙이 있으면 게임 길이가 다항으로 강제되어 PSPACE에 떨어진다"는 한 줄짜리 직관이 꽤 자주 들어맞는다.

5. 마무리

2인 완전정보 게임의 결정 문제를 양화 부울식의 진리 판정과 한 줄로 잇는 데 성공했다. 그 결과 TQBF가 누리던 PSPACE-완전성은 깔끔한 가젯 환원을 통해 일반화 지오그래피로 전염되었고, 그 너머로 Hex와 같은 보드게임에까지 번져 있다.

1. 메모리 한 줌으로 무엇을 할 수 있는가

이쯤 되면 자원의 단위가 점점 작아진다. 다항 시간, 다항 공간을 거쳐 이제 우리가 다룰 자원은 로그 공간이다. 입력 길이가 n이라면 작업 테이프는 O(log n) 칸. 직관적으로는 입력에 대한 인덱스를 몇 개 들고 있을 정도의 메모리. 이 좁은 방 안에서도 의외로 많은 일이 일어난다.

왜 입력 테이프를 빼는가? log n은 입력을 한 번 통째로 적어 두기에도 부족한 양이다. 입력 자체를 공간에 포함시키면 log 공간이라는 정의가 거의 무의미해진다. 따라서 입력은 "외부 세계"로 두고 작업 메모리만 측정하는 모형이 표준이다.

당연히 L ⊆ NL. 그리고 한 단계 더.

이 한 줄짜리 보조 정리, "형태 그래프의 크기가 다항"이 NL을 다룰 때마다 반복적으로 등장한다. 잘 외워 두면 뒤이은 모든 증명의 토대가 된다.

2. PATH: 로그 공간 비결정성의 표본

고전적 BFS로는 다항 시간에 풀린다. 하지만 공간 측면에서는? 방문한 정점을 표시할 비트맵을 만드는 순간 |V| 비트가 필요하니 로그 공간을 넘어선다. 그래서 PATH가 L에 들어가는지는 미해결이다. 반면 비결정적이라면 사정이 다르다.

"정점 두 개를 메모리에 들고 있다 + 카운터" — 이 셋이 NL의 가장 정직한 그림이다.

3. 로그 공간 환원과 NL-완전성

NL 안에서 "가장 어려운" 문제를 잡으려면 환원의 척도도 NL과 어울리는 자원이어야 한다. 다항 시간 환원은 NL을 비교하기엔 너무 강력하다(다항 시간이면 NL 전체를 안에 품으니, 환원이 너무 많은 일을 해 버린다).

로그 공간 환원의 결정적 합성이 다시 로그 공간이라는 사실(주의를 요하는 보조 정리지만 표준)이, 이 환원이 NL의 자연스러운 척도임을 보장한다.

4. 의외의 등식: NL = coNL

NP의 여집합 클래스 coNP가 NP와 같은지는 50년이 지나도 미해결이다. 같은 질문을 NL에 던지면 어떨까? 1987년, Immerman과 Szelepcsényi가 독립적으로 NL = coNL을 증명했다. NP에서는 안 풀린 일이 NL에서는 풀린 셈이다.

이 정리를 보이는 데에는 NL-완전 PATH의 여집합, 즉

NPATH = { (G, s, t) : G에 s에서 t로 가는 방향 경로가 없다 }

이 NL에 들어감을 보이면 충분하다. PATH가 NL-완전이므로 PATH의 여집합이 NL에 들어가면 모든 coNL 언어가 NL에 들어간다.

5. 핵심 발상: 정확한 카운트가 있으면 부정도 추측 가능

비결정주의가 풀어야 하는 어려움은 "어떤 게 없다"를 어떻게 증인 없이 받아들이느냐이다. 그러나 한 가지 우회로가 있다. s에서 도달 가능한 정점의 수 R을 정확히 알면, 그 R개를 모두 비결정적으로 열거하면서 그 안에 t가 없음을 확인하는 것으로 "t는 도달 불가"를 검증할 수 있다.

구체적으로 다음을 보자.

6. R을 비결정적으로 세는 법: 인덕티브 카운팅

남은 일은 R을 NL 안에서 손에 넣는 것. 핵심은 정점이 아닌 거리 단계별로 세는 것이다.

R_i = "s에서 i 단계 이내에 도달 가능한 정점의 수".

R₀ = 1이고(자기 자신만 도달), R = R_|V|이다. R₀에서 R_|V|까지 하나씩 갱신해 가는데, 갱신 단계에서도 비결정성을 활용한다.

R_i−1이 손에 있다고 하자. R_i를 구하려면 각 정점 v마다 "v가 i 단계 안에 도달 가능한가?"를 결정해야 하는데, 비결정주의로는 양성 사실(도달 가능)만 직접 증명할 수 있다. 그래서 다음 관찰을 쓴다.

v가 i단계 안에 도달 가능 ⇔ v가 (i−1)단계 안에 도달 가능, 또는 v의 어떤 입접 정점 u가 (i−1)단계 안에 도달 가능.

알고리즘은 정점 v를 한 명씩 처리하며 다음을 한다. (i−1)단계 도달 가능 정점들을 R_i−1개 비결정적으로 열거하고 각각의 경로를 검증한다 — 보조 정리에서 한 트릭과 같은 골격. 그 과정에서 어떤 도달 가능 u가 v의 입접 이웃이거나 u = v이면 "v는 i단계 도달 가능"이라 표시. 모든 정점에 대해 표시 여부를 합산해 R_i를 얻는다.

각 정점에 대한 처리 메모리도 O(log n), 모든 정점을 한 명씩 처리하므로 동시에 들고 있어야 할 데이터는 (현재 v, 카운터, 검증용 임시 정점) 정도 — 여전히 O(log n). 거리 i도 |V|까지만 가니 카운터 한 개. 결국 전체가 NL 안에 들어간다.

7. 함의의 의외성

P vs NP, NP vs coNP는 풀리지 않은 채 수십 년이 흘렀다. 그런데 한 단계 아래로 내려와 NL을 보니, 1987년의 두 사람이 같은 질문을 깔끔히 정리해 버렸다. 비결정성과 부정 사이의 비대칭성이 자원이 작아질수록 약해진다는 사실은, 복잡도 이론의 직관 하나를 흔드는 일이었다. "비결정성의 본질적 비대칭"이 보편 진리가 아니라, 시간 다항이라는 특정 자원에서만 나타나는 특수한 현상일 가능성을 열어 둔 셈.

1. 자명해 보이지만 자명하지 않은 질문

"자원을 두 배로 늘려 주면 풀 수 있는 문제가 정말로 늘어날까?" 이 질문에 1초도 망설이지 않고 "그럼"이라 답하고 싶지만, 형식적으로 따지자면 그리 단순하지 않다. 시간 n²로는 풀 수 없는데 n³로는 풀리는 문제가 진짜 있어야 자원의 의미가 살아난다. 그런 문제가 존재한다는 것을 어떻게 보일까?

이 강의에서 만날 위계 정리(hierarchy theorem)들은 그 답이다. 시간을 늘리면 정말로 새로운 언어가 결정 가능해지고, 공간을 늘리면 정말로 새로운 언어가 인식 가능해진다. 다만 "얼마나 늘려야 하는가"의 양적 조건이 달려 있고, 함수가 적당히 잘 행동해야 한다.

일상에서 만나는 거의 모든 "정상적인" 함수 — n², n log n, 2ⁿ 등 — 는 두 종류 모두에 들어간다. 구성 가능성은 시뮬레이터가 시계나 자처럼 자원 한도를 셀 수 있어야 한다는 기술적 요청이다.

2. 시간 위계 정리

"f를 한 단계 키워 g로 가면, 진짜로 더 많은 언어를 결정할 수 있다"는 정확한 형태다. 왜 단순히 f(n) = o(g(n))이 아니라 f(n) log f(n)이 끼어드는지가 증명에서 자연스럽게 드러난다. 보편 시뮬레이터가 어떤 TM을 흉내 낼 때 log 인자만큼의 오버헤드가 든다는 사실이 그 출처다.

3. 증명의 핵심: 대각선화

증명의 도구는 칸토어가 실수의 비가산성을 보일 때 쓴 것과 본질이 같은 대각선화다. 우리는 g(n) 시간에는 결정 가능하지만 어떤 f(n)-시간 TM도 결정할 수 없는 언어를 손수 만든다.

다음 TM D를 정의하자. 입력 ⟨M⟩ — TM M의 인코딩 — 에 대해

1. 입력 길이 n을 보고 g(n)을 시간 구성 가능성을 이용해 카운터에 적어 둔다.
2. M을 입력 ⟨M⟩ 위에 시뮬레이션하되, g(n) 시간이 지나기 전까지만 돌린다. 시계가 만료되면 시뮬레이션을 중단.
3. 시간 안에 M이 멈췄고 받아들였다면 D는 거부; 멈췄고 거부했다면 D는 받아들임; 시간이 만료되었다면 거부.

핵심 두 사실.

사실 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 M₀도 존재하지 않는다. 만약 존재한다면, 충분히 큰 n에서 M₀의 동작이 g(n) 시간 안에 끝나도록 할 수 있다(f log f = o(g)). 입력 ⟨M₀⟩(또는 같은 언어를 결정하는 충분히 긴 인코딩)을 D에 넣으면, D의 정의에 의해 D(⟨M₀⟩) = ¬M₀(⟨M₀⟩). 그러나 M₀이 D를 결정한다면 D(⟨M₀⟩) = M₀(⟨M₀⟩). 모순. □

4. 공간 위계 정리

시간 위계와 비교하면 조건이 깔끔하다. 그저 f(n) = o(g(n))이면 충분하고, log 오버헤드가 없다. 이유는 단순. 공간은 재사용이 자유로운 자원이라 공간 시뮬레이션의 오버헤드는 상수배에 그친다. 한 셀을 천 번 다시 쓰든 자원이 늘지 않는다. 시간은 그렇지 않다. 한 단계는 한 번이고, 시뮬레이터의 내부 데이터구조 검색에 log가 자연스레 따라붙는다.

공간 위계의 증명도 같은 골격이다. g(n) 공간 시계를 들고 ⟨M⟩ 위에서 M을 시뮬레이션하다가 공간을 초과하면 멈춘다. 결과를 뒤집어 출력. 마찬가지로 어떤 f(n)-공간 기계도 이 언어를 결정할 수 없다. 한 가지 추가 주의는 공간 한계 시뮬레이션에서 무한 루프를 피하기 위해 형태 수가 2^O(g(n))로 한정됨을 이용해 시계도 함께 도는 것 — 같은 형태가 두 번 나오면 정지로 간주.

5. 따름정리: 강력한 분리

위계 정리들은 추상적으로 보일 수 있으나, 곧장 구체적인 클래스 분리로 이어진다.

이 두 분리는 직관적으로는 "그야 당연히 그렇겠지" 싶지만, 형식적인 증명을 위해서는 위계 정리의 대각선화가 반드시 필요하다는 사실을 짚어 두고 싶다. 추가로, P와 EXPTIME 사이를 채우는 클래스들 — NP, PSPACE — 가운데 어딘가에 진짜 ⊊가 일어난다는 것은 알지만, 어디인지는 모른다.

6. 한계: 위계 정리로 풀리지 않는 것

위계 정리는 같은 자원 종류 안에서 양적 차이가 클 때만 분리를 보장한다. 여기서 자연스럽게 떠오르는 한계들.

자원 종류가 다르면 직접 적용 불가. P와 NP는 모두 다항 시간이지만, 비결정성이라는 정성적 차이를 가진다. 위계 정리는 결정적 시간 안에서의 양적 분리, 비결정적 시간 안에서의 양적 분리만 직접 말해 준다. 두 종류의 시간을 가로지르는 분리는 다른 도구가 필요하다 — 그리고 그 도구가 아직 없다.

같은 종류 안에서도 격차가 작으면 무력. P vs PSPACE는 양쪽이 모두 결정적이지만, P는 다항 시간을, PSPACE는 다항 공간을 다룬다. 다항 시간 ⇒ 다항 공간이지만 그 역은 미해결. 시간과 공간을 잇는 위계는 별도의 미해결 영역이다.

릴라티비제이션 장벽. 60년대 후반 Baker–Gill–Solovay는 oracle A를 잘 골라 P^A = NP^A를 만들 수도, P^B ≠ NP^B를 만들 수도 있음을 보였다. 위계 정리의 대각선화는 oracle 아래에서도 그대로 작동한다(시뮬레이션이 oracle을 그대로 통과). 따라서 P vs NP는 단순한 대각선화 논증으로는 풀 수 없다는 강력한 신호. 이것이 relativization barrier다. P와 NP 사이의 진짜 분리(혹은 등식)는 더 정교한 도구가 필요하다는 메시지로 받아들여진다.

7. 마무리

이 강의에서는 자원의 의미를 정량적으로 굳혔다. 시간을 한 단계 늘리면 (log 인자를 감안하고) 진짜로 새 언어가 풀리고, 공간도 마찬가지다. 그 결과 P ⊊ EXPTIME, PSPACE ⊊ EXPSPACE 같은 가장 자연스러운 분리가 안전하게 손에 들어왔다. 동시에, P vs NP, P vs PSPACE 같은 작은 격차의 클래스 분리는 위계 정리의 손이 닿지 않는 영역임을 확인했다.

1. 위계 정리가 약속한 것

지난 강의들에서 우리는 P, NP, PSPACE, EXPTIME 같은 클래스들을 차곡차곡 쌓아 올렸지만, 이 클래스들이 정말로 서로 다른지에 대해서는 대부분 침묵해 왔다. P ≠ NP는 여전히 수수께끼이고, NP ≠ PSPACE조차 미해결이다. 그러나 시간 위계 정리(time hierarchy theorem)와 공간 위계 정리(space hierarchy theorem)는 단 하나의 확실한 분리를 우리에게 선물한다. 충분히 큰 격차가 있으면 자원을 더 주는 쪽이 진짜로 더 많은 것을 한다는 사실이다.

특히 공간 위계 정리는 PSPACE ⊊ EXPSPACE를 직접 보여 준다. 다시 말해, 다항 공간으로는 절대로 풀 수 없지만 지수 공간으로는 풀리는 언어가 자연 속에 존재한다. 위계 정리는 보통 대각선화로 만든 인공적 언어를 분리 증인으로 사용하는데, 이 강의의 첫 번째 목표는 그 추상적 분리를 구체적 자연 문제에 끼워 넣는 것이다.

2. EQ_REX↑: 다항 공간으로는 도달할 수 없는 자연 문제

정규 표현식의 표준 연산자 집합 ∪, ·, ∗에 더해서 제곱 연산자 ↑를 추가하자. 식 R↑은 R · R, 즉 R을 두 번 이어 붙인 것을 줄여 쓴 것이다. 이런 확장 정규 표현식 두 개가 같은 언어를 나타내는지 묻는 문제를 다음과 같이 정의한다.

제곱 연산자는 사소해 보이지만, 식 ((R↑)↑)↑ … ↑는 R을 2^k번 이어 붙인 식과 동치다. 즉 ↑는 길이 n짜리 입력으로 길이 2ⁿ까지의 문자열을 다루는 표현력을 끌어올린다. 이 폭발적 표현력 덕분에 EQ_REX↑은 EXPSPACE 안에서 해결되지만 — 표준 동치성 검사를 지수 크기 NFA에 대해 시뮬레이션 — PSPACE로는 절대 잡히지 않는다.

증명의 골자는 임의의 EXPSPACE 기계 M의 계산 이력을 길이 2^p(n)짜리 정규 표현식 두 개로 인코딩한 뒤, "M이 수락한다"는 사실이 "이 두 식이 다른 언어를 나타낸다"와 동치임을 보이는 다항 시간 환원이다. 위계 정리가 EXPSPACE에 의해 PSPACE 바깥에 있는 무언가를 보장하므로, EXPSPACE-완전 문제는 자동으로 PSPACE-바깥이 된다. 우리는 비로소 "구체적이고 자연스러운, 그러나 다항 공간으로는 절대 못 푸는" 문제를 손에 쥔 것이다.

3. 신탁 튜링 기계의 정의

이제 시점을 바꿔, 우리가 어려운 문제를 해결한 마법 동전을 가지고 있다고 가정하자. 그 동전의 이름이 신탁(oracle)이다.

신탁은 결과만을 알려 주지 그 결과를 어떻게 얻었는지는 절대 말하지 않는다. 신탁의 능력은 자원 측정에서 무료다. 따라서 P^A는 "A를 단위 시간에 묻는 다항 시간 결정 TM이 결정하는 언어들의 집합"이고, NP^A는 같은 비결정 변종이다.

4. Baker–Gill–Solovay 정리

신탁의 진짜 매력은 P 대 NP 문제를 우회적으로 살펴보게 해 준다는 데 있다. 1975년 Baker, Gill, Solovay는 다음의 충격적 사실을 증명했다.

5. 함의: 상대화 장벽

왜 이 정리가 그토록 큰 무게를 가지는가? 우리가 P 대 NP를 푸는 데 사용해 온 거의 모든 도구 — 시뮬레이션, 대각선화, 환원 — 는 "신탁을 그냥 통과해 적용된다"는 의미에서 상대화(relativizing)된다. 만약 어떤 증명이 P = NP를 보였다면, 그 증명을 신탁 B에 넣어도 같은 결론이 나와야 한다. 그런데 P^B ≠ NP^B! 따라서 P = NP는 상대화 가능한 기법으론 절대 증명될 수 없다. 마찬가지로 P ≠ NP의 증명은 신탁 A에 적용했을 때 P^A ≠ NP^A를 강제할 텐데, 우리는 P^A = NP^A를 보았다. 즉 양쪽 결론 모두 상대화 기법의 사거리 밖에 있다.

6. 다음 강의 예고

상대화의 그늘에서 벗어나는 한 가지 길은 우연을 도구로 끌어들이는 것이다. 결정적 시뮬레이션이 아닌 동전 던지기로 푸는 문제 — 이 무작위 계산이 다음 강의 BPP의 무대다. 신탁이 가능성에 대한 사고 실험이라면, 무작위성은 그 실험을 실제로 수행하는 알고리즘이다.

1. 결정성을 포기한 대가

지금까지 우리가 다룬 모든 모델은, 비결정성을 포함하더라도, "옳은 답"이라는 단일 진리치에 매달려 있었다. 이번 강의에서는 그 진리치를 살짝 흔든다. 알고리즘에게 동전을 쥐여 주고, 답이 틀릴 가능성을 작게나마 허용하자. 놀랍게도 이 사소해 보이는 양보가 그래프, 정수론, 행렬, 부울 함수 등 많은 영역에서 결정적 알고리즘으로는 흉내 내기 어려운 효율을 가져온다.

같은 입력에 대해 같은 기계가 시도 때마다 다른 답을 줄 수 있다는 것이 핵심이다. 그러므로 우리가 해야 할 일은 이 변덕을 제어하는 정의를 세우는 것이다. 가장 자연스러운 후보는 다음의 양면 오류(two-sided error) 모델이다.

2. BPP의 정의

2/3과 1/3 사이의 간격은 신중하게 설정된 신호대잡음비(signal-to-noise ratio)다. 만약 두 임계값이 1/2의 양옆이 아니라 1/2 위아래로 임의로 가까우면, 다수결 증폭을 통한 신뢰도 향상이 망가진다. 그러나 일단 1/3 만큼이라도 떨어져 있으면, 우리는 이 간격을 천문학적으로 벌릴 수 있다.

3. 오차 증폭과 체르노프 한계

같은 PTM M을 독립적으로 k번 실행해 다수결을 취하자. 각 실행은 정답에 한 표를 던지는 베르누이 변수와 같다. 정답률이 2/3이면 평균은 2k/3, 거짓 답을 다수결이 채택하려면 평균에서 k/6만큼 어긋나야 한다. 체르노프 한계(Chernoff bound)는 이런 큰 일탈의 확률이 지수적으로 작음을 보장한다.

다시 말해 BPP의 정의에서 "2/3"이 별것 아니다. 1/2 + 1/poly(n)부터 1 − 2⁻ⁿ까지 상수나 다항 만큼 오차 한계를 다양하게 잡아도 같은 클래스다. 무작위 알고리즘의 신뢰도는 무한히 살 수 있는 상품이다.

4. 일면 오류와 영면 오류: RP, coRP, ZPP

오차의 종류에 따라 BPP를 더 엄격하게 좁힐 수 있다.

관용적 직관: RP의 기계와 coRP의 기계를 동시에 돌리고, 둘의 답이 일치할 때까지 다시 시도한다. 두 답이 결정적 진실을 끼고 있을 때 일치할 확률은 적어도 1/2이므로 평균 두 번 시행이면 충분하다. 어떤 답이 나오든 그 답은 무조건 옳다.

5. BPP는 어디에 있는가?

BPP를 결정적 클래스로 시뮬레이션하려면 모든 동전 시퀀스를 차례로 시도해 보면 된다. 다항 시간 PTM은 다항 길이의 동전 시퀀스를 사용하므로, 그 모두에 대해 수락/거절을 카운트하면 된다.

역방향 포함 PSPACE ⊆ BPP에 대해서는 아무도 모른다. P ⊆ BPP ⊆ PSPACE라는 거대한 띠 안에서 BPP의 정확한 위치는 미해결 문제다.

6. Schwartz–Zippel과 다항식 동등성 검사

BPP의 위력을 가장 우아하게 보여 주는 예가 다항식 동등성(polynomial identity testing, PIT)이다. 두 다항식이 같은지 묻는 문제는 — 식이 산술 회로로 압축되어 주어지면 — 결정적으로 폭발할 수 있다. 그러나 Schwartz–Zippel 보조정리는 단숨에 우리를 구한다.

7. Miller–Rabin과 PRIMES

현실 세계에서 BPP의 가장 빛나는 사례는 소수 판별이었다. Miller–Rabin 검사는 페르마 소정리와 비자명 제곱근의 부재를 무작위로 검증해, 합성수를 확률 1/4 이상으로 잡아낸다. k번 반복하면 거짓 양성 확률이 4^−k로 떨어진다. 이는 PRIMES ∈ coRP를 보장한다.

8. 정리

이번 강의에서 우리는 동전을 손에 쥔 알고리즘을 형식화하고, 그 신뢰도를 무한히 끌어올릴 수 있음을 체르노프 한계로 확인했다. RP, coRP, ZPP가 BPP 안에 박혀 있고, 모두 PSPACE 아래에 있다. PIT와 PRIMES는 무작위성이 결정성보다 본질적으로 더 강한지, 아니면 단지 우리의 분석이 미흡한지에 대한 질문을 우리에게 던진다. 이 질문이 다음 강의의 출발점이다.

1. BPP를 가두는 다항 위계

지난 강의에서 BPP ⊆ PSPACE를 보았지만, 이 한계는 너무 헐렁하다. PSPACE는 우주의 컴퓨팅 자원을 모두 모아도 풀 수 없는 거인들을 잔뜩 품고 있는 클래스이고, BPP는 우리가 매일 굴리는 무작위 알고리즘들의 집이다. 더 정밀한 한계가 필요하다. 그것이 1983년 Sipser와 Gács, 그리고 Lautemann이 독립적으로 증명한 다음 정리다.

이 결과의 묘미는 무작위성이라는 양적인 자원을 ∃와 ∀라는 논리적인 자원으로 환산해 낸다는 데 있다. 직관은 다음과 같다. L ∈ BPP에 대한 PTM M의 동전 시퀀스 r은 길이 m = poly(n)의 비트열이다. 입력 x ∈ L에 대한 "수락 동전 집합" A_x = { r : M(x; r) accepts }는 {0, 1}^m의 적어도 99%를 차지하도록 증폭할 수 있고, x ∉ L이면 1% 이하다.

이제 비결정적 ∃∀ 한 쌍을 다음처럼 설계한다. 충분히 큰 t = m + 1에 대해, 비트열 t-튜플 (s₁, …, s_t)이 주어지면 "이 t개의 시프트로 A_x의 평행이동 합집합이 {0, 1}^m 전체를 덮는다"는 술어를 본다. A_x가 거대하면 적당한 (s₁, …, s_t)이 존재해 모든 r ∈ {0, 1}^m에 대해 어떤 i가 있어 M(x; r ⊕ s_i)이 수락한다. 반대로 A_x가 작으면, 어떤 t-튜플로도 덮을 수 없는 r이 항상 존재한다.

이 결과의 한 가지 그림 같은 함의: P = NP라면 다항 위계 전체가 P로 무너지고, 따라서 BPP ⊆ P. 즉 P 대 NP 추측은 무작위성의 가치 추측까지 동시에 결정한다.

2. BPP = P 추측과 의사난수성

현재의 압도적 추측은 BPP = P이다. 즉 모든 무작위 알고리즘은 (다항 시간 추가 비용으로) 결정성으로 환원될 수 있다는 것이다. 이 추측의 진지한 근거는 의사난수 생성기(pseudo-random generator, PRG)의 존재다.

좋은 PRG가 있다면 BPP 알고리즘의 동전 m비트를 G의 시드 s(n) ≪ m비트로 대체한 뒤, 모든 시드를 결정적으로 시도하면 된다. 시뮬레이션 비용은 2^s(n)·poly(n)인데, 충분히 강한 회로 가정 — 예컨대 SAT가 지수적 회로를 요구한다 — 아래에서 s(n) = O(log n)인 PRG가 존재하므로 결정적 다항 시간 시뮬레이션이 가능해진다. Impagliazzo–Wigderson(1997)은 이러한 가정 아래 BPP = P를 증명했다. 무작위성은, 따라서, 단순히 "쉬운 문제 X 어려운 회로 가정"으로 환산되는 자원이다.

3. Adleman 정리와 비균일 조언

다른 방향에서 BPP의 결정화를 시도하자. 시간 자원만으로는 어렵다면, 비균일 조언을 허락하면 어떨까?

따라서 길이 n의 모든 입력에 동시에 옳은 답을 주는 동전 시퀀스 r^∗_n이 적어도 하나 존재한다. 이 r^∗_n을 길이 n 입력에 대한 다항 길이 조언 문자열로 사용하면, 결정적 다항 시간 회로(혹은 조언 받는 TM)가 L을 결정한다. 즉 BPP는 비균일 모델에서는 다항 회로의 위력을 넘지 못한다.

4. 무작위 환원과 RP-완전성

결정성 환원 ≤_p를 무작위로 일반화한 것이 무작위 다항 시간 환원 ≤_r이다. A ≤_r B란, A의 멤버십을 답하는 다항 시간 PTM이 존재해 B에 대한 단일 질의로 답하되 양측 오류가 1/3 이하라는 뜻이다. RP-완전, BPP-완전 같은 개념이 정의될 수 있지만, BPP가 자기-환원과 잘 어울리는 promise 클래스인 탓에 BPP-완전 언어는 표준적인 의미에서 존재하지 않는다 — 이는 BPP가 syntactic 클래스가 아니라 semantic 클래스임을 보여 주는 미묘한 사실이다.

5. 그래프 비동형성: BPP의 자연스러운 거주민

BPP의 자연 예제 중 가장 사랑받는 것은 그래프 비동형성(GRAPH NON-ISOMORPHISM, GNI)이다.

6. 다음 강의 예고

지금까지 우리는 검증자가 무작위성을 사용하되 외부와 상호작용하지 않는 모델을 다뤘다. 검증자가 동전을 가지고 무한 능력의 증명자와 대화를 나누면 어떤 일이 벌어지는가? 이 단순한 한 가지 변화가 PSPACE 전체를 검증 가능 클래스로 끌어올린다. 다음 강의에서 등장하는 IP, 상호작용 증명 시스템이 그 무대다. 우리는 NP의 정적 인증서가 무작위성을 만났을 때 어떻게 살아 움직이는지를 본다.

1. NP의 한계, 그리고 그 너머

NP를 다시 떠올려 보자. 검증자 V는 다항 시간 결정 TM이고, 증명자가 보낸 단 하나의 인증서 w를 읽고 수락 또는 거절한다. V는 동전도 없고 P와 두 번째 메시지를 주고받지도 않는다. 이 정적 모델은 우아하지만, 매우 경직되어 있다. SAT 같은 문제는 잘 다루지만, "어떤 조건이 성립하지 않는다"는 종류의 진술 — coNP — 에 대해서는 짧은 인증서를 일반적으로 알지 못한다.

이 강의에서 우리는 검증자에게 두 가지 새로운 자원을 동시에 준다. 첫째, 무작위 동전. 둘째, 증명자와의 다항 라운드 대화. 그 결과 클래스가 IP다. 놀랍게도 IP는 NP보다 단순히 큰 정도가 아니라, PSPACE 전체와 같다(다음 강의에서 증명). 우선 정의부터.

2. IP의 형식적 정의

NP의 두 변경점이 모두 결정적이다. V의 동전은 P가 모르는 무작위성을 V에게 주고, 다항 라운드의 대화는 V가 P의 답에 따라 다음 도전을 적응적으로 만들 수 있게 한다. P가 무한 능력이라는 가정 — 결국 어떤 PSPACE 문제도 풀어 줄 수 있다 — 도 핵심이다. P는 진실을 알고 있고, V는 그 진실을 검증하기만 하면 된다.

완전성/건전성의 1/3과 2/3은 BPP에서처럼 증폭으로 1 − 2⁻ⁿ 수준까지 끌어올릴 수 있다. 같은 프로토콜을 독립적으로 여러 번 평행 또는 직렬로 돌려 다수결을 취하면 된다. 단 평행 반복이 건전성을 항상 보존하지는 않는다는 미묘함은 다항 라운드 IP의 분석에서 중요한 주제다.

3. NP ⊆ IP는 자명하다

그렇다면 IP의 진짜 위력은 어디서 오는가? coNP 같은 클래스에서 온다. 다음 절의 예제는 IP가 단순히 NP를 흉내 내는 것이 아니라, 짧은 인증서가 알려져 있지 않은 문제까지 검증할 수 있음을 보여 주는 고전이다.

4. 그래프 비동형성 ∈ IP

두 그래프 G₁ = (V, E₁), G₂ = (V, E₂)가 주어졌을 때 동형이 아니라는 것을 어떻게 짧게 증명할 것인가? 동형이라는 사실에는 짧은 인증서(순열)가 있지만, 동형이 아니라는 사실에는 자연스러운 짧은 인증서가 없다. 그러나 다음 IP 프로토콜은 단 두 라운드로 GNI를 검증한다.

5. 왜 무작위성이 핵심인가

위 프로토콜에서 V의 동전 b와 π를 P가 미리 알고 있다고 상상해 보자. 그러면 P는 H를 받기도 전에 b'를 정확히 답할 수 있다. 건전성은 즉시 무너진다. 즉 V의 동전이 P에게 비밀로 남아 있어야만 P가 속이지 못한다. 이런 의미에서 IP에서 무작위성은 단순한 효율 도구가 아니라 안전 메커니즘이다.

또 다른 시각으로 말하자면, V의 동전은 P를 시험하기 위한 동적 도전을 무한히 생성하는 엔진이다. 정적 NP 인증서가 한 번의 시험이라면, IP는 P를 매번 새로운 무작위 도전 앞에 세우는 면접관의 역할을 V에게 부여한다.

6. Arthur–Merlin과 공개 동전 모델

IP의 동전은 V에게 비밀이다. 동전을 모두 공개하는 변종 — 공개 동전 모델 — 도 자연스러운 정의를 낳는다. 이를 Arthur–Merlin 게임이라 한다. Arthur(V)가 매 라운드 동전을 던져 그 결과를 그대로 메시지로 보내고, Merlin(P)이 응답한다.

이 정리의 직관: V가 비밀 동전을 사용한다면, V는 동전 시퀀스의 분포가 자기 메시지에 대해 충분히 균등함을 P에게 통계적으로 증명할 수 있다. 비밀스러움은 전체 클래스의 표현력에 영향을 주지 않는, 다소 외형적인 차이임이 드러난다. 단, 라운드 수가 상수일 때는 AM[k]의 위계가 특정 깊이에서 무너진다 — AM[2] = AM[k] for any constant k ≥ 2 — 라는 부수적 사실도 유명하다.

7. 다음 강의 예고

지금까지 우리는 IP의 정의와 첫 비자명한 거주민 GNI를 보았다. 다음 강의에서 우리는 더 야심찬 목표 — coNP ⊆ IP — 을 LFKN의 산술화 기법과 SUM-CHECK 프로토콜로 직접 증명한다. 그리고 이 기법이 전부 PSPACE까지 확장될 때 IP = PSPACE라는 1992년의 대정리에 도달한다. NP의 좁은 정적 모델을 떠난 우리는, 검증의 한계가 사실은 PSPACE만큼 멀다는 것을 보게 된다.

1. 마지막 산

지난 강의에서 우리는 GNI ∈ IP를 통해 IP가 NP를 진정으로 넘어선다는 첫 증거를 보았다. 이번 강의의 목표는 훨씬 더 멀다.

한 방향 IP ⊆ PSPACE는 비교적 쉽다 — V의 결정과 P의 최적 메시지를 다항 공간 안에서 게임 트리 탐색으로 시뮬레이션할 수 있다. 어려운 방향은 PSPACE ⊆ IP. 이 강의에서는 그 출발점이자 핵심 기법을 다 보여 주는 부분 — coNP ⊆ IP — 를 자세히 살펴본 뒤, 그 기법이 PSPACE 전체로 확장되는 모습을 스케치한다. 출발 도구는 1990년 Lund–Fortnow–Karloff–Nisan(LFKN)이 도입한 산술화(arithmetization)다.

2. #SAT와 산술화

UNSAT — 부울 식 φ가 충족 불가능한가? — 는 coNP-완전이다. 우리는 이를 더 일반적인 카운팅 문제 #SAT로 환원해 다룬다.

산술화의 핵심. 부울 식 φ(x₁, …, x_n)을 변수가 정수 또는 유한체 𝔽_p 위의 값을 가질 수 있는 다변수 다항식 f_φ로 바꾼다. 변환 규칙은 다음처럼 기계적이다.

• 변수 x → x.
• ¬x → 1 − x.
• x ∧ y → x · y.
• x ∨ y → x + y − xy. (즉 1 − (1−x)(1−y).)

이 변환은 부울 입력 (b₁, …, b_n) ∈ {0, 1}ⁿ에 대해 f_φ(b₁, …, b_n) = [φ(b₁, …, b_n) = 참] 를 보장한다. 따라서 충족 할당 수는

#φ = ∑_{x1 ∈ {0,1}} ∑_{x2 ∈ {0,1}} ⋯ ∑_{xn ∈ {0,1}} f_φ(x₁, …, x_n).

UNSAT은 #φ = 0이라는 주장과 동치다. 이로써 부울 만족 문제는 다변수 다항식 위 합의 값에 대한 주장으로 환산된다. 다항식의 차수는 φ 길이에 대해 다항이다 — 정확히 절(節) 수에 비례. 이 다항식 표현은 작은 일탈에도 민감해서, 무작위 한 점에서의 평가가 전체를 식별하는 강력한 지표가 된다(Schwartz–Zippel).

3. SUM-CHECK 프로토콜

이제 IP 프로토콜을 설계해, 다항 시간 V가 P의 도움으로 ∑_{x ∈ {0,1}ⁿ} f(x) = K 라는 주장을 검증하게 만들자. 작업장은 충분히 큰 유한체 𝔽 = 𝔽_p이고, p는 충족 할당 수의 상한 2ⁿ보다 훨씬 큰 소수로 잡는다(예 p = 2³ⁿ).

핵심 발상: P가 한 번에 모든 변수의 합을 V에게 증명할 수 없으니, 변수 하나를 다항식으로 풀어 V에게 보내고 V가 무작위 점 r을 골라 한 변수씩 제거해 가는 라운드 기반 검증.

완전성. #φ가 진짜로 K이면 정직한 P는 매 라운드의 정확한 g_i를 보낼 수 있고, 모든 등식이 성립해 V는 항상 수락. 마지막 평가도 일치한다.

건전성. 진짜 합이 K가 아닌데 어떤 P̃가 V를 속이려 한다고 하자. 첫 라운드에서 P̃는 진짜 g₁와 다른 다항식 g̃₁를 보내야 한다 — 안 그러면 g₁(0) + g₁(1) = K가 거짓을 폭로한다. 그러나 g̃₁ ≠ g₁은 차수 d₁의 두 다항식이 서로 다름을 의미하므로, 무작위 r₁에서 두 식이 같을 확률은 d₁/|𝔽| 이하(Schwartz–Zippel).

그래서 r₁이 "운 좋게" 두 다항식의 일치점을 짚지 않는 이상, 두 번째 라운드의 새 약속 K₁ = g̃₁(r₁)도 진짜와 어긋나 같은 일이 반복된다. 모든 n 라운드를 통과하려면 매 라운드 d_i/|𝔽| 정도의 운이 필요하다. 합집합 한계로 V가 속을 확률 ≤ ∑_i d_i/|𝔽| ≤ n · d / |𝔽|. |𝔽|를 2³ⁿ으로 잡으면 이 값은 1/3보다 훨씬 작다.

다시 말해, P̃의 거짓말은 매 라운드 다항식 사이의 격차를 만들고, 그 격차는 무작위 점에서 거의 확실히 검출된다. 한 번 검출된 거짓말은 V의 마지막 직접 평가에서 결정적으로 폭로된다.

4. coNP ⊆ IP

이 결과는 NP가 coNP를 단순히 흉내낼 수 없는 정적 모델임에 비추어 충격적이다. 비대화 NP에서는 UNSAT의 짧은 인증서가 알려져 있지 않은데, 동전 + 다항 라운드의 대화가 있으면 검증이 가능해진다. 이는 다음 강의의 자연스러운 확장으로 이어진다.

5. PSPACE까지의 확장

위 기법을 PSPACE-완전 문제 TQBF로 확장하면 IP = PSPACE의 어려운 방향이 따라온다. TQBF는 ∀x₁ ∃x₂ … φ(x₁, …, x_n) 형태의 양화된 부울 식의 진리값을 묻는다. ∃-양화자는 합 ∑로, ∀-양화자는 곱 ∏로 산술화하면 다음 표현을 얻는다.

⟦ψ⟧ = ∑_{x1 ∈ {0,1}} ∏_{x2 ∈ {0,1}} ⋯ f_ψ(x₁, …, x_n).

그러나 곱 연산은 다항식의 차수를 입력 길이에 대해 지수적으로 키워 SUM-CHECK의 차수 분석을 망가뜨린다. Shamir의 1992년 핵심 아이디어는 라운드 사이에 축약 연산자(linearization operator) L_i를 끼워 넣는 것이다. L_i는 변수 x_i에 대해 다항식을 강제로 1차로 줄여 두며 — x_i ∈ {0, 1}에서의 값에 의해 1차 다항식이 결정되므로 — 차수 폭발을 막아 준다. 이 트릭으로 다항 라운드, 다항 차수의 SUM-CHECK 같은 프로토콜이 TQBF에 적용 가능하고, 결과적으로 PSPACE ⊆ IP. 다른 방향 IP ⊆ PSPACE은 V와 최적 P를 PSPACE 시뮬레이션으로 평가할 수 있다는 사실에서 따라온다. 따라서 두 클래스가 정확히 일치한다.

6. 한 학기의 결산

한 학기를 한 바퀴 돌아 우리는 다음 풍경을 그렸다. 가장 작은 모델 — 정규 언어, 결정적 유한 오토마타 — 에서 출발해 비결정성과 폐쇄 연산을 거쳐 문맥 자유 문법에 도착했다. 펌핑 보조정리들은 이 작은 모델들의 한계를 드러냈고, 우리는 무한 메모리 — 튜링 기계 — 로 사다리를 한 칸 올랐다. 거기서 결정 가능과 인식 가능이 갈렸고, 정지 문제와 환원의 기술은 결정 불가능성의 지도를 그려 주었다.

그다음 자원의 양을 측정하는 시점으로 돌아와 시간 위계와 공간 위계를 세웠다. P, NP, PSPACE, EXPTIME, EXPSPACE — 그 사이의 거리는 일부 확실하고 일부 미궁이다. 환원과 완전성은 이 미궁 안의 길잡이로, SAT, TQBF, EQ_REX↑ 같은 자연 문제들에 정확한 어려움의 좌표를 부여했다.

마지막 몇 강의에서 우리는 결정성을 흔들었다. 동전을 던지는 BPP, 다항 위계로 한정되는 BPP의 거주지, 비균일 조언이 흡수하는 무작위성. 그리고 검증자가 동전과 대화를 동시에 가지면 IP = PSPACE라는 거대한 동치까지. 무작위성은 단순한 효율 도구가 아니라 검증의 본질을 바꾸는 자원이었다.

이 한 바퀴의 핵심 메시지는 단 하나다. 계산은 자원으로 잴 수 있고, 그 자원의 종류를 바꿀 때마다 새로운 풍경이 열린다. 시간, 공간, 무작위성, 상호작용, 비균일성 — 우리는 이 다섯을 손에 쥐고 풀 수 있는 것과 풀 수 없는 것의 경계를 매번 조금씩 다시 그렸다. P 대 NP, BPP 대 P, NP 대 PH 같은 미해결 추측들은 이 풍경 안에 빈자리로 남아 있다. 그 빈자리를 메우는 일이, 계산이론을 떠나며 여러분에게 남기는 우리 분야의 손짓이다. 강의는 끝이지만, 질문은 막 시작이다.