강의 17

공간 복잡도, PSPACE, 그리고 사비치 정리

시간이 아니라 메모리를 자원으로 셀 때, 결정성과 비결정성의 격차는 한 변의 제곱이라는 작은 값으로 좁혀진다.

1. 자원의 축을 바꾸기

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

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

정의 (공간 복잡도 클래스). 함수 s : ℕ → ℕ에 대해

SPACE(s(n)) — 모든 입력 길이 n에 대해 작업 테이프 칸을 최대 s(n)개만 사용하고 항상 정지하는 결정적 튜링 기계로 결정 가능한 언어들의 집합.
NSPACE(s(n)) — 같은 정의에서 비결정적 기계를 허용한 것. 어떤 분기든 작업 테이프 사용량이 s(n) 이하라야 한다.

다항 공간.
PSPACE = ⋃_{k ≥ 1} SPACE(n^k), NPSPACE = ⋃_{k ≥ 1} NSPACE(n^k).

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

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

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

관찰 1. 임의의 함수 t(n)에 대해 TIME(t(n)) ⊆ SPACE(t(n)).

증명. t(n) 단계 안에 정지하는 기계는 그 동안 헤드가 t(n)칸 이상 움직일 수 없다. 따라서 작업 테이프에서 실제로 방문되는 칸도 t(n)개를 넘지 못한다.

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

관찰 2. s(n) ≥ log n에 대해 SPACE(s(n)) ⊆ TIME(2^O(s(n))).

증명 스케치. 작업 공간이 s 칸이면 가능한 구성(상태, 작업 테이프 내용, 작업 헤드 위치, 입력 헤드 위치)의 총 수는 |Q| · |Γ|^s · s · n으로, 2^O(s)(s ≥ log n이라 n도 흡수된다). 정지하는 기계는 같은 구성을 두 번 방문하지 않으므로 — 만약 그랬다면 무한 루프 — 총 단계 수는 구성 개수를 넘지 못한다.

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

   P  ⊆  NP  ⊆  PSPACE  ⊆  EXPTIME

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

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

3. PSPACE의 대표 시민: TQBF

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

정의 (TQBF). 전 양화 부울 식(totally quantified boolean formula)은 다음 모양이다.

  φ = Q₁ x₁  Q₂ x₂  …  Q_k x_k  ψ(x₁, …, x_k)

여기서 각 Q_i는 ∀ 또는 ∃이고 ψ는 양화자 없는 부울 식이다. 자유 변수가 없으므로 φ는 그 자체로 참 또는 거짓이다. TQBF는 참인 전 양화 부울 식들의 집합이다.

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

정리. TQBF ∈ PSPACE.

증명 스케치. 다음 재귀 알고리즘 EVAL(φ)을 정의한다.

φ에 양화자가 없으면 ψ를 직접 계산해 결과를 돌려준다 — 다항 공간.
φ = ∃x₁ φ'(x₁)이면 EVAL(φ'[x₁ := 0])과 EVAL(φ'[x₁ := 1])을 차례로 호출, 둘 중 하나라도 참이면 참을 돌려준다.
φ = ∀x₁ φ'(x₁)이면 같은 두 호출의 결과가 모두 참인 경우에만 참을 돌려준다.

각 호출은 다음 호출에 들어가기 전에 필요한 작업 공간을 회수한다. 즉 우리는 같은 다항 공간을 재사용한다. 호출 깊이는 변수 개수 k이고 k는 입력 크기에 의해 다항으로 한정된다. 따라서 총 작업 공간은 (한 레벨의 공간) × (깊이) = 다항.

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

두 명이 두는 게임. ∃ 측은 자기 차례마다 변수에 0 또는 1을 골라 두고, ∀ 측은 자기 차례마다 변수를 골라 둔다. 마지막에 ψ가 참이면 ∃ 승, 거짓이면 ∀ 승. φ가 TQBF에 속한다는 것은 정확히 "∃ 측에 필승 전략이 있다"는 진술이다. 체스나 바둑처럼 양 진영이 번갈아 두는 게임이 PSPACE에 등장하는 데에는 그럴 만한 이유가 있다.

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

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

사비치 정리 (Savitch 1970). s(n) ≥ log n에 대해 NSPACE(s(n)) ⊆ SPACE(s(n)²).

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

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

술어 CANYIELD(c₁, c₂, t). N의 구성 c₁에서 c₂로 t 단계 안에 (혹은 c₁ = c₂이고 t = 0으로) 도달 가능한가?

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

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

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

정리의 증명 스케치. N의 NSPACE(s) 기계가 입력 w를 수락하면 그 수락 경로의 길이는 구성의 총 수에 의해 한정되어 2^O(s) 이내. 따라서 c_start에서 c_accept로 가는 경로가 있으려면 t = 2^O(s)로 두고 CANYIELD(c_start, c_accept, t)를 묻는 것으로 충분하다.

이를 결정적 기계로 구현한다. 모든 가능한 수락 구성 c_accept에 대해 CANYIELD(c_start, c_accept, 2^O(s))가 참인지 차례로 시도한다. 재귀 깊이는 log(2^O(s)) = O(s), 한 레벨당 공간은 O(s). 따라서 총 작업 공간은

  O(s) × O(s) = O(s²).

바깥쪽 c_accept 순환은 카운터 하나로 돌리고 매번 같은 작업 공간을 재활용하므로 추가 비용이 없다.

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

따름정리. PSPACE = NPSPACE.

증명. NSPACE(n^k) ⊆ SPACE((n^k)²) = SPACE(n^2k) ⊆ PSPACE. 따라서 NPSPACE = ⋃_k NSPACE(n^k) ⊆ PSPACE. 반대 포함은 자명.

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

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

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

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

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