계산 이력을 부울 수식으로 옮겨 적으면, 모든 NP 문제는 결국 한 장의 진리표 위에 놓인다.
NP-완전성이라는 개념을 처음 정의했을 때 한 가지 의문이 따라붙는다. NP-완전 문제가 정말 존재하긴 하는가? 정의상 그것은 NP에 속하면서, NP의 모든 문제가 자기 자신으로 다항 시간 환원되는 거대한 자석 같은 문제다. 누군가가 그 자석을 한 번이라도 만들어 보여 주지 않는다면, 클래스의 정의는 공허할 수도 있다.
1971년 스티븐 쿡과 1973년 레오니드 레빈이 독립적으로 이 자석을 직접 손에 쥐여 주었다. 그 자석의 이름이 바로 SAT(boolean satisfiability problem, 부울식 충족성 문제)이다. SAT는 변수들의 논리식이 주어졌을 때 그 식을 참으로 만드는 할당이 존재하는지를 묻는 결정 문제다. 결과는 충격적으로 단순하면서도 깊다.
(1)은 거의 자명하다. 식 φ가 주어지고 누군가 만족 할당 τ를 인증서로 건네주면, τ를 φ에 대입해 결과가 참인지 다항 시간에 확인하면 된다. 검증자는 한 줄 평가기 그 이상도 이하도 아니다. 흥미로운 부분은 (2)다. 임의의 NP 언어 A를 SAT로 환원해야 한다 — 그것도 A의 정의에 대해 거의 아무것도 모르는 채로 말이다.
A가 NP 언어라 하자. 정의에 의해 A를 결정하는 비결정적 튜링 기계(NTM) N과 다항식 t(n)이 존재해서, 입력 w(길이 n)에 대해 N은 t(n) 단계 안에 어떤 비결정 분기를 따라 수락 여부를 끝낸다. 우리가 만들 환원은 다음 한 줄로 요약된다.
다시 말해 φw의 만족 할당이란 곧 "N이 w를 어떻게 받아들이는가"의 청사진이다. 변수는 청사진의 각 칸이고, 절(clause)은 그 청사진이 진짜 N의 동작 규칙을 따르는 합법적 이력임을 강제한다.
이제 실제로 청사진의 종이를 펼쳐 보자. 입력 길이가 n일 때 t(n)을 그저 t로 줄여 적는다. 우리는 가로 t칸, 세로 t칸짜리 격자(tableau)를 그린다. 행 인덱스 i는 시간(0행이 초기, t-1행이 종료), 열 인덱스 j는 테이프 위치다. 각 칸 ⟨i, j⟩에 들어갈 내용은 다음 두 가지 중 하나다.
한 행을 좌에서 우로 읽으면 한 시각의 전체 구성(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 등장 ... |
이 격자가 합법적인 수락 이력이라는 사실을 부울식으로 옮기는 데 필요한 변수와 절은 다음과 같다.
이제 우리는 변수들의 진리값이 진짜 격자를 묘사하도록 강제하는 절들을 적는다. 이를 네 그룹으로 나누어 부른다 — cell, start, accept, move.
먼저 각 칸이 적어도 하나의 내용은 가지고, 그러나 두 가지를 동시에 가지지 않게 만들어야 한다. 칸 ⟨i, j⟩에 대해
( ⋁s ∈ C xi,j,s ) ∧ ( ⋀s ≠ t ¬xi,j,s ∨ ¬xi,j,t )
전자는 "무엇이든 적혀 있다", 후자는 "두 글자가 동시에 적혀 있을 수는 없다"는 뜻이다. 칸이 t2개이고 각 칸의 절 길이는 |C|에 의해 정해지므로, 이 그룹의 총 절 개수는 O(t2)이다.
입력 w = w1 w2 … wn이 주어졌을 때, 0행은 정확히 다음 모양이어야 한다.
x0, 0, ⟨q0, w1⟩ ∧ x0, 1, w2 ∧ … ∧ x0, n-1, wn ∧ x0, n, ⊔ ∧ … ∧ x0, t-1, ⊔
(한 줄짜리 합접이라 절 하나로 표현하기 어색해 보이면, 각 합접 항을 단일 리터럴 절로 따로따로 두면 된다.) 이 그룹의 절 개수는 O(t)이다.
N이 w를 수락한다는 사실은 이력 어딘가에 수락 상태 qaccept가 등장했다는 뜻이다. 격자의 어느 칸이든 좋다.
⋁i, j, s ∈ Γ xi, j, ⟨qaccept, s⟩
거대한 OR 절 하나로 충분하며 길이는 O(t2)이다. (전이 후 정지하는 NTM이라 가정하면 헤드가 일단 qaccept에 도달하면 그 자리에 머무는 식으로 다듬을 수 있다.)
가장 중요한 그룹이다. 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(t2)이다.
네 그룹을 모두 합접으로 묶으면 우리의 부울식 φw가 완성된다.
φw = φcell ∧ φstart ∧ φaccept ∧ φmove
다항성도 따져 보자. 변수 개수는 O(t2), 절 개수는 cell·start·accept·move 모두 합쳐 O(t2)에 N에 의존하는 상수가 곱해진 정도다. φw를 종이에 적는 일은 입력 w를 훑으며 격자 좌표를 따라 출력하는 것이라 다항 시간에 끝난다. 따라서 환원 자체가 다항 시간에 가능하다 — A ≤p SAT.
SAT의 절은 임의 길이를 허용하지만, 실전에서는 한 절의 리터럴 수가 정확히 셋인 3SAT이 환원의 표준 출발점이 되는 일이 많다. 다행히 SAT가 NP-완전이라는 사실로부터 3SAT가 NP-완전임을 잇는 다리는 짧다.
(l1 ∨ l2 ∨ z1) ∧ (¬z1 ∨ l3 ∨ z2) ∧ … ∧ (¬zk-3 ∨ lk-1 ∨ lk)
로 쓴다. 길이가 1 또는 2인 절은 변수 하나를 복제해 길이 3에 맞춘다. 보조 변수의 진리값은 "지금까지의 어느 li도 참이 아니라면, 다음 절을 만족시키기 위한 책임을 떠넘긴다"는 신호로 작동한다. 원래 절이 만족되면 적절한 z 할당이 존재하고, 반대로 변환된 합접이 만족되면 어떤 li가 참이어야 한다(그렇지 않으면 z들의 충돌로 자명히 모순).
변환 후 절 개수는 원본의 합 길이에 비례해 다항이다. 따라서 SAT ≤p 3SAT, 그리고 임의 NP 언어 A는 A ≤p SAT ≤p 3SAT.
쿡-레빈 정리의 진짜 가치는 그 자체보다 그것이 열어 주는 통로에 있다. 새로운 결정 문제 B의 NP-완전성을 보이고 싶다고 하자. 정의에 따르면 모든 NP 언어가 B로 환원됨을 보여야 하는데, 이는 매번 NTM의 격자를 들고 와 사투를 벌이라는 뜻이다. 그러나 SAT 또는 3SAT가 NP-완전이라는 사실을 손에 쥐고 있으면, 우리는 한 가지만 보이면 된다.
이로써 이후의 모든 NP-완전성 증명은 "어디서 출발할까" 하는 카탈로그 게임이 된다. 첫 번째 NP-완전 문제를 정직하게 만들어 둔 쿡과 레빈의 수고가 그 카탈로그의 맨 윗 줄을 지탱하고 있는 셈이다.
다음 강의에서는 시간에서 공간으로 무대를 옮긴다. 메모리만 다항이면 시간이 지수여도 괜찮다는 클래스 PSPACE를 정의하고, 비결정적 공간이 결정적 공간과 본질적으로 다르지 않다는 사비치(Savitch) 정리를 만난다 — 시간 영역의 P 대 NP 문제가 공간에서는 한 변의 제곱 차이로 깔끔하게 해결되는, 약간 짓궂은 광경이 펼쳐진다.