1. 메모리 한 줌으로 무엇을 할 수 있는가
이쯤 되면 자원의 단위가 점점 작아진다. 다항 시간, 다항 공간을 거쳐 이제 우리가 다룰 자원은 로그 공간이다. 입력 길이가 n이라면 작업 테이프는 O(log n) 칸. 직관적으로는 입력에 대한 인덱스를 몇 개 들고 있을 정도의 메모리. 이 좁은 방 안에서도 의외로 많은 일이 일어난다.
정의 20.1 (로그 공간 TM). 입력 테이프(읽기 전용)와 작업 테이프를 분리한 2-테이프 튜링 기계 M을 생각하자. M의 공간 사용량은 작업 테이프에서 사용한 칸 수만 센다. 입력 테이프 자체는 공간으로 치지 않는다. M이 모든 입력 길이 n에서 O(log n) 작업 공간만 사용하면, 그것을 로그 공간 TM이라 한다.
왜 입력 테이프를 빼는가? log n은 입력을 한 번 통째로 적어 두기에도 부족한 양이다. 입력 자체를 공간에 포함시키면 log 공간이라는 정의가 거의 무의미해진다. 따라서 입력은 "외부 세계"로 두고 작업 메모리만 측정하는 모형이 표준이다.
정의 20.2.
- L = SPACE(log n): 결정적 로그 공간 TM이 결정하는 언어들의 클래스.
- NL = NSPACE(log n): 비결정적 로그 공간 TM이 인식하는 언어들의 클래스.
당연히 L ⊆ NL. 그리고 한 단계 더.
정리 20.3. NL ⊆ P.
증명. 비결정적 로그 공간 TM M의 형태(configuration)는 (상태, 작업 테이프 내용, 입력 헤드 위치, 작업 헤드 위치)로 인코딩된다. 작업 테이프 길이는 O(log n), 헤드 위치는 각각 log n 비트. 따라서 형태 하나의 크기가 O(log n)이고, 가능한 형태 수는 2O(log n) = nO(1)로 다항이다. 형태 그래프(정점 = 형태, 간선 = 1단계 전이)를 명시적으로 만든 뒤, 시작 형태에서 받아들임 형태로의 도달 가능성을 BFS로 확인하면 다항 시간에 끝난다. 따라서 L(M) ∈ P. □
이 한 줄짜리 보조 정리, "형태 그래프의 크기가 다항"이 NL을 다룰 때마다 반복적으로 등장한다. 잘 외워 두면 뒤이은 모든 증명의 토대가 된다.
2. PATH: 로그 공간 비결정성의 표본
정의 20.4 (PATH). 입력은 방향 그래프 G와 정점 쌍 (s, t). 질문은 "G에 s에서 t로 가는 방향 경로가 존재하는가?". 이 언어를 PATH라 한다.
고전적 BFS로는 다항 시간에 풀린다. 하지만 공간 측면에서는? 방문한 정점을 표시할 비트맵을 만드는 순간 |V| 비트가 필요하니 로그 공간을 넘어선다. 그래서 PATH가 L에 들어가는지는 미해결이다. 반면 비결정적이라면 사정이 다르다.
정리 20.5. PATH ∈ NL.
증명. 다음 비결정적 알고리즘을 고려하자. 현재 정점 v를 s로 초기화. 카운터 i를 0으로 초기화. i ≤ |V|인 동안 다음을 반복: 만약 v = t이면 받아들임. 그렇지 않으면 v의 이웃 중 하나 v′을 비결정적으로 추측하고 v ← v′, i ← i + 1. i가 |V|를 초과하면 거부.
각 정점은 log |V| = O(log n) 비트, 카운터도 마찬가지. 작업 메모리 총량은 O(log n)이다. s에서 t로 경로가 존재하면 그것을 추측하는 수용 분기가 있고, 없으면 어느 분기도 받아들이지 않는다. □
"정점 두 개를 메모리에 들고 있다 + 카운터" — 이 셋이 NL의 가장 정직한 그림이다.
3. 로그 공간 환원과 NL-완전성
NL 안에서 "가장 어려운" 문제를 잡으려면 환원의 척도도 NL과 어울리는 자원이어야 한다. 다항 시간 환원은 NL을 비교하기엔 너무 강력하다(다항 시간이면 NL 전체를 안에 품으니, 환원이 너무 많은 일을 해 버린다).
정의 20.6 (로그 공간 환원). 함수 f: Σ* → Σ*가 로그 공간으로 계산 가능하다는 것은, 입력 테이프에 w를 받고 출력 테이프에 f(w)를 적는 결정적 TM이 작업 테이프 O(log |w|)만 사용함을 말한다. 출력 테이프는 한 방향 쓰기 전용이라 출력 자체는 공간에 포함하지 않는다. A ≤L B는 어떤 로그 공간 환원 f가 존재해 w ∈ A ⇔ f(w) ∈ B가 되는 것을 의미한다.
로그 공간 환원의 결정적 합성이 다시 로그 공간이라는 사실(주의를 요하는 보조 정리지만 표준)이, 이 환원이 NL의 자연스러운 척도임을 보장한다.
정리 20.7. PATH는 NL-완전이다(≤L 기준).
증명 스케치. 멤버십은 위에서 보았다. 경도: 임의의 A ∈ NL과 비결정적 로그 공간 TM M을 받자. M의 형태 그래프 GM,w를 만들면(정점 = 형태, 간선 = 가능한 비결정적 전이) A의 멤버십은 GM,w에서 시작 형태로부터 받아들임 형태로의 도달 가능성과 동치. 형태 하나는 O(log n) 비트이므로, 형태 한 개의 인코딩을 작업 메모리에 두고 한 비트씩 출력 테이프에 흘리면서 정점/간선을 차례로 적어 내려갈 수 있다. 각 시점에 들고 있는 메모리는 형태 두 개 정도 — O(log n)에 머문다. 따라서 환원은 로그 공간이며, 결과 그래프 위의 PATH 질문이 w ∈ A와 동치. □
잠깐, 익숙한 패턴이다. NP-완전 SAT를 보일 때도 우리는 "TM의 계산표를 그래프 비슷한 식으로 인코딩한 뒤 도달 가능성을 묻는다"는 발상을 썼다. 이번엔 시간 표가 아니라 형태 그래프, 식이 아니라 그래프 도달성. 자원의 종류만 갈아 끼웠을 뿐 골격은 같다.
4. 의외의 등식: NL = coNL
NP의 여집합 클래스 coNP가 NP와 같은지는 50년이 지나도 미해결이다. 같은 질문을 NL에 던지면 어떨까? 1987년, Immerman과 Szelepcsényi가 독립적으로 NL = coNL을 증명했다. NP에서는 안 풀린 일이 NL에서는 풀린 셈이다.
정리 20.8 (Immerman–Szelepcsényi). NL = coNL. 즉 모든 NL 언어의 여집합도 NL에 속한다.
이 정리를 보이는 데에는 NL-완전 PATH의 여집합, 즉
NPATH = { (G, s, t) : G에 s에서 t로 가는 방향 경로가 없다 }
이 NL에 들어감을 보이면 충분하다. PATH가 NL-완전이므로 PATH의 여집합이 NL에 들어가면 모든 coNL 언어가 NL에 들어간다.
5. 핵심 발상: 정확한 카운트가 있으면 부정도 추측 가능
비결정주의가 풀어야 하는 어려움은 "어떤 게 없다"를 어떻게 증인 없이 받아들이느냐이다. 그러나 한 가지 우회로가 있다. s에서 도달 가능한 정점의 수 R을 정확히 알면, 그 R개를 모두 비결정적으로 열거하면서 그 안에 t가 없음을 확인하는 것으로 "t는 도달 불가"를 검증할 수 있다.
구체적으로 다음을 보자.
보조 정리 20.9. 어떤 절차가 입력 (G, s) 위에서 도달 가능 정점 수 R을 작업 메모리 안에 적어 줄 수 있다고 하자. 그러면 NPATH ∈ NL.
증명. R이 손에 있다고 가정. 다음을 한다. 카운터 k를 0으로. G의 모든 정점 v를 차례로 훑으며, 각 v에 대해 비결정적으로 "이 정점이 s에서 도달 가능하다"라고 주장하거나 건너뛴다. 주장한다면 s에서 v로 가는 경로를 길이 ≤ |V|로 비결정적으로 추측해 검증하고, 만약 v = t이면 즉시 거부(도달 가능한 정점 중에 t가 있다는 뜻이므로). 검증 성공하면 k ← k + 1. 모든 정점을 돌고 나서 k = R이면 받아들임, 아니면 거부.
만약 t가 진짜 도달 불가이면, 도달 가능한 R개 정점을 정확히 골라 검증하는 분기가 존재하고 그동안 한 번도 t를 만나지 않으므로 k = R로 받아들인다. 만약 t가 도달 가능이면, R개를 모은다는 것은 어디선가 반드시 t를 거쳐야 한다는 뜻이라 항상 거부된다. 메모리는 정점 두어 개 + 카운터 + R 자체이므로 O(log n). □
6. R을 비결정적으로 세는 법: 인덕티브 카운팅
남은 일은 R을 NL 안에서 손에 넣는 것. 핵심은 정점이 아닌 거리 단계별로 세는 것이다.
Ri = "s에서 i 단계 이내에 도달 가능한 정점의 수".
R0 = 1이고(자기 자신만 도달), R = R|V|이다. R0에서 R|V|까지 하나씩 갱신해 가는데, 갱신 단계에서도 비결정성을 활용한다.
Ri−1이 손에 있다고 하자. Ri를 구하려면 각 정점 v마다 "v가 i 단계 안에 도달 가능한가?"를 결정해야 하는데, 비결정주의로는 양성 사실(도달 가능)만 직접 증명할 수 있다. 그래서 다음 관찰을 쓴다.
v가 i단계 안에 도달 가능 ⇔ v가 (i−1)단계 안에 도달 가능, 또는 v의 어떤 입접 정점 u가 (i−1)단계 안에 도달 가능.
알고리즘은 정점 v를 한 명씩 처리하며 다음을 한다. (i−1)단계 도달 가능 정점들을 Ri−1개 비결정적으로 열거하고 각각의 경로를 검증한다 — 보조 정리에서 한 트릭과 같은 골격. 그 과정에서 어떤 도달 가능 u가 v의 입접 이웃이거나 u = v이면 "v는 i단계 도달 가능"이라 표시. 모든 정점에 대해 표시 여부를 합산해 Ri를 얻는다.
각 정점에 대한 처리 메모리도 O(log n), 모든 정점을 한 명씩 처리하므로 동시에 들고 있어야 할 데이터는 (현재 v, 카운터, 검증용 임시 정점) 정도 — 여전히 O(log n). 거리 i도 |V|까지만 가니 카운터 한 개. 결국 전체가 NL 안에 들어간다.
증명 결론. R = R|V|을 NL에서 계산할 수 있고, R을 손에 두면 NPATH ∈ NL. PATH가 NL-완전이므로 임의의 coNL 언어를 NL의 PATH-여집합 인스턴스로 환원해 NL 안에서 풀 수 있다. 따라서 coNL ⊆ NL. NL ⊆ coNL은 같은 논증을 여집합 양쪽으로 돌려 얻으며, 결국 NL = coNL. □
왜 NP에서는 같은 트릭이 안 통하는가. NP의 카운트 버전 #SAT(만족하는 부여의 수)를 정확히 안다면 coNP를 NP 안에서 다룰 수 있다. 그러나 #SAT를 NP 안에서 정확히 세는 방법이 없다. 형태 공간이 지수라 "거리 i까지 도달 가능 정점 수"의 NL 트릭이 NP에서는 너무 비싸다. 좁은 메모리가 오히려 무기가 되어 준다는 점이 이 정리의 묘미다.
7. 함의의 의외성
P vs NP, NP vs coNP는 풀리지 않은 채 수십 년이 흘렀다. 그런데 한 단계 아래로 내려와 NL을 보니, 1987년의 두 사람이 같은 질문을 깔끔히 정리해 버렸다. 비결정성과 부정 사이의 비대칭성이 자원이 작아질수록 약해진다는 사실은, 복잡도 이론의 직관 하나를 흔드는 일이었다. "비결정성의 본질적 비대칭"이 보편 진리가 아니라, 시간 다항이라는 특정 자원에서만 나타나는 특수한 현상일 가능성을 열어 둔 셈.
다음 강의 다리. 그렇다면 자원을 더 주면 정말로 더 많이 할 수 있는가 — 시간을 두 배로, 공간을 한 줌 더 — 라는 가장 원초적인 질문으로 돌아가자. 위계 정리(hierarchy theorem)가 이 직관에 어떤 보장을 주고, 어떤 한계에서 멈추는지가 다음 강의의 주제다.