다항 공간의 가장 어려운 문제들, 그리고 TQBF가 그 자리에 앉는 이유
NP에서 SAT가 차지했던 위치를 떠올려 보자. SAT 하나만 잘 풀면 NP 전체가 무너지는, 그런 압도적 위치 말이다. PSPACE에서도 똑같은 그림을 그릴 수 있다. 다만 자원이 시간이 아니라 공간이라는 점만 다를 뿐이다. 이번 강의의 주연은 TQBF(True Quantified Boolean Formula, 참인 양화 부울식)이고, 조연은 Savitch 정리에서 이미 한 번 만난 재귀적 분할이다.
왜 환원의 척도로 "다항 시간"을 쓰는가? PSPACE라는 더 큰 그릇 안에서 의미 있는 비교를 하려면, 환원 자체는 비교 대상보다 훨씬 약한 자원으로 묶어 두어야 한다. 시간 다항이면 공간도 다항이므로, 다항 시간 환원은 PSPACE 내부의 구조를 충분히 보존한다.
다시 말해, PSPACE-완전 문제 한 마리만 효율적으로 잡아도 다항 시간으로 다항 공간 전체를 정복하는 셈이다. 그래서 PSPACE-완전성은 단순히 어렵다는 라벨이 아니라, "이 한 점이 무너지면 클래스 전체가 무너진다"는 절단점의 의미를 갖는다.
SAT가 ∃만 쓰는 양화식의 진리 판정이라면, TQBF는 ∃와 ∀가 자유롭게 교차한다. 양화자가 한 번 더 끼어들 때마다 "결정 한 단계"가 더해지고, 게임으로 치면 수가 한 번 더 두어지는 셈이다.
증명은 두 부분으로 나뉜다. 한 쪽은 쉬운 멤버십, 다른 한 쪽은 핵심 어려움이다.
먼저 멤버십. 입력 φ = Q1x1 … Qnxn ψ를 받았다고 하자. 재귀적으로 평가한다. φ의 가장 바깥 양화자가 ∃x1이면 x1 = 0과 x1 = 1을 차례로 시도해 둘 중 하나라도 참이면 참을 반환한다. ∀x1이면 둘 다 참이어야 참을 반환한다. 양화자가 모두 사라지면 ψ를 직접 계산한다.
재귀 깊이는 양화자의 개수 n이고, 각 단계에서 부분 식의 사본 대신 변수 할당만 기억하면 된다. 따라서 공간 사용량은 O(n + |φ|), 즉 n의 다항이다. 이 단순한 깊이 우선 평가만으로 TQBF ∈ PSPACE.
이제 어려운 방향이다. 임의의 A ∈ PSPACE를 받아, A ≤p TQBF임을 보여야 한다. PSPACE TM M이 입력 w에서 공간 s = nk를 쓴다고 하자(여기서 n = |w|). 우리의 임무는 다항 시간에 양화 부울식 φM,w를 구성해 다음을 만족시키는 것이다.
φM,w가 참 ⇔ M이 w를 받아들임.
M의 형태(configuration)는 길이 O(s) = O(nk) 비트로 인코딩된다. Cook–Levin 식 발상으로, 시작 형태 cstart에서 받아들임 형태 caccept까지의 형태 수열을 통째로 변수화하면? M의 실행 시간은 최대 2O(s)이다(공간 한계 TM의 정지성을 위해). 형태 수열은 그러므로 길이 2O(s), 변수 개수도 2O(s). 식 크기가 지수가 되어 다항 시간 환원이 깨진다. 단순 인코딩은 실패한다.
해법은 시간이 아니라 중간점을 양화로 잡아내는 것이다. 두 형태 c1, c2와 단계 수 t에 대해, "c1에서 c2로 ≤ t 단계에 갈 수 있다"를 표현하는 식 φc1,c2,t를 재귀적으로 만든다.
기저 t = 1: φc1,c2,1은 c1 = c2이거나 c1이 한 단계로 c2에 가는지 확인하는, Cook–Levin식 국소 검증 식. 크기는 O(s).
재귀 단계: 직관적으로는
∃m [ φc1,m,t/2 ∧ φm,c2,t/2 ]
이라고 쓰고 싶지만, 이 형태는 재귀가 한 단계 내려갈 때마다 식이 두 배가 된다. 깊이 log T = O(s)이므로 결국 다시 지수 폭발이다.
핵심 트릭은 ∀를 이용해 두 부분 식을 같은 식 하나로 합치는 것이다.
φc1,c2,t ≡ ∃m ∀(a,b) ∈ {(c1,m), (m,c2)} φa,b,t/2.
여기서 ∀(a,b) ∈ {…}는 두 가지 형태 쌍에 대한 양화이며, 새 변수 (a,b)를 도입한 뒤 "(a,b)가 (c1,m) 또는 (m,c2)이면 φa,b,t/2가 성립" 같은 함의로 풀어 쓴다. 이렇게 하면 재귀 호출이 식 안에 두 번 등장하는 대신 한 번만 등장한다.
각 재귀 단계에서 식 크기는 다음 점화식을 만족한다.
L(t) = L(t/2) + O(s), L(1) = O(s).
풀면 L(T) = O(s · log T) = O(s2). 다항이다. 양화자의 깊이도 log T = O(s) = O(nk)로 다항이다. 마지막으로
φM,w ≡ φcstart, caccept, T
로 두면 φM,w가 참 ⇔ M이 w를 받아들임. 환원 자체는 형태 인코딩과 재귀적 식 생성이 전부이므로 다항 시간에 끝난다. 따라서 TQBF는 PSPACE-완전이다. □
이쯤에서 그림을 정리하자. 다음 포함 관계는 모두 알려진 사실이다.
P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ EXPSPACE.
등호는 Savitch 정리, NPSPACE ⊆ EXPTIME은 형태 그래프 크기가 2poly임에서 곧바로 따른다. 이 사슬에서 어느 두 인접 클래스가 진짜로 같은지 다른지는 대부분 미해결이지만, 다음 강의에서 공부할 위계 정리는 P ⊊ EXPTIME과 PSPACE ⊊ EXPSPACE를 확정해 준다. 따라서 위 사슬에서 적어도 한 곳은 진짜 ⊊이다. 단지 어디인지를 모를 뿐.
마지막으로, TQBF를 게임이라는 다른 렌즈로 보자. φ = ∃x1 ∀x2 ∃x3 … ψ를 두 플레이어의 대국으로 읽자. ∃ 차례에는 플레이어 E가 변수를 0/1로 둔다. ∀ 차례에는 플레이어 A가 둔다. 모든 변수가 결정되면 ψ를 평가한다. ψ가 참이면 E의 승리, 거짓이면 A의 승리.
그러면 φ가 참이라는 것은 정확히 E가 승리 전략을 갖는다는 뜻이다. 게임 트리의 minimax 평가가 곧 양화식의 재귀적 평가다. ∃는 max, ∀는 min, 잎은 ψ의 진리값. 다항 깊이의 minimax 트리 위에서 누가 이기는가 — 이 질문이 PSPACE의 가장 어려운 문제와 같은 난도라는 사실은, 다음 강의에서 일반화 지오그래피와 보드게임으로 곧장 이어진다.