강의 15

NP-완전성 — 어려움의 가장 단단한 핵

문제 하나가 무너지면 모두가 무너진다. 그것이 완전(complete)이라는 단어의 무게다.

1. NP-난해와 NP-완전

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

정의 15.1 (NP-난해). 언어 B가 NP-난해(NP-hard)라는 것은 모든 A ∈ NP에 대해 A ≤p B가 성립한다는 것이다. 즉 B는 NP의 어떤 문제보다도 적어도 같은 만큼 어렵다.
정의 15.2 (NP-완전). 언어 B가 NP-완전(NP-complete)이라는 것은 다음 두 조건을 모두 만족하는 것이다:
  1. B ∈ NP.
  2. B는 NP-난해.

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

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

정리 15.3. B가 NP-완전이고 B ∈ P이면, P = NP.
B가 NP-난해이므로 임의의 A ∈ NP에 대해 A ≤p B. 그리고 B ∈ P. 지난 강의의 정리에 의해 A ∈ P. A는 NP의 임의의 원소였으므로 NP ⊆ P. 반대 방향 P ⊆ NP는 자명하므로 P = NP. ∎

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

그래서 알고리즘 설계자들은 어떤 새 문제를 만나면 가장 먼저 그것이 NP-완전인지 의심한다. 만약 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|.

정확성 스케치. G에 정점 부분 집합 S(|S| = k)가 있을 때, S가 G의 클리크 ⟺ S 안의 모든 쌍이 G의 간선 ⟺ S 안의 어떤 쌍도 G̅의 간선이 아님 ⟺ V ∖ S가 G̅의 모든 간선을 덮는다(왜냐하면 G̅의 간선은 양 끝 중 적어도 하나가 V ∖ S에 있어야만 가능하므로) ⟺ V ∖ S는 G̅의 정점 덮개. |V ∖ S| = n − k. 따라서 G의 k-클리크 ⟺ G̅의 (n − k)-덮개. ∎

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

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

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

구성 스케치. 각 다이아몬드는 양쪽 끝에 한 정점씩, 가운데에 m × 2 + 3 정도의 칸이 늘어선 “두 줄 사다리”다. 다이아몬드 안을 통과하는 해밀턴 경로는 두 방향(왼쪽→오른쪽 또는 오른쪽→왼쪽) 중 하나로만 진행할 수 있는데, 이 두 방향이 변수의 두 진리값에 대응한다.

각 절 cj의 노드는, cj에 등장하는 리터럴마다 해당 변수 다이아몬드의 적절한 위치와 연결된다. xi가 cj에 양의 리터럴로 나타나면, xi의 다이아몬드가 “참” 방향으로 통과될 때만 cj 노드를 잠시 들렀다 돌아올 수 있도록 간선을 단다. 부정 리터럴이면 “거짓” 방향에서 들를 수 있게 한다.

해밀턴 경로는 모든 다이아몬드를 어떤 방향으로 통과해야 하고(변수 대입을 결정), 각 절 노드를 정확히 한 번씩 방문해야 한다(각 절이 만족됨). 따라서 ϕ가 만족 가능 ⟺ G에 s에서 t로의 해밀턴 경로 존재. ∎

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

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

구성 스케치. 무방향 간선 (vin, vmid)와 (vmid, vout)를 둔다. G에서 (u, v)가 방향 간선이면, G′에서 무방향 간선 (uout, vin)을 둔다. 출발점 s는 sout로, 도착점 t는 tin으로 매핑한다(또는 in/out 구분 보조 정점 추가).

G′에서 해밀턴 경로는 어떤 정점 v에 들어가더라도 vin → vmid → vout 순서로만 통과할 수 있다 — vmid의 이웃이 vin과 vout 둘뿐이므로. 따라서 무방향 경로는 사실상 G의 방향 간선을 따라가는 경로와 일대일 대응한다. ∎

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

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

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

구성 스케치. 자릿수는 두 부분으로 나뉜다. 왼쪽 n자리는 변수 x1, …, xn에 하나씩, 오른쪽 m자리는 절 c1, …, cm에 하나씩. 변수 xi마다 두 수 yi(xi = 참)와 zi(xi = 거짓)를 만든다. yi는 변수 자릿수 xi 위치에 1, xi가 양의 리터럴로 들어 있는 절 자릿수에 1을 두고, 나머지는 0. zi는 대칭적으로 xi 자릿수에 1, ¬xi가 들어 있는 절 자릿수에 1.

추가로 각 절 cj에 “보충(slack)” 두 수 gj, hj를 두는데, 둘 다 cj 자릿수에만 1과 2를 둔다(또는 1을 두 개). 목표 합 t는 변수 자릿수에 모두 1, 절 자릿수에 모두 3.

자릿올림이 발생하지 않도록 자릿수 사이 간격을 충분히 두는 것이 핵심이다(변수당 최대 합이 한 자리 안에 머무르도록). 그러면 부분 집합 합이 t를 만들기 위해 각 변수에 대해 yi나 zi 중 정확히 하나를 골라야 하고(변수 자릿수에서 1을 채워야 하니까), 그 선택이 변수 대입에 대응한다. 절 자릿수의 3을 채우려면 그 절을 만족하는 리터럴이 적어도 하나 필요하다(보충 두 수가 최대 2까지 채워주므로 리터럴에서 적어도 1은 와야 한다). 따라서 ϕ가 만족 가능 ⟺ 합 t를 만드는 부분 집합 존재. ∎

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

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

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

정리 15.4 (≤p의 추이성). A ≤p B 이고 B ≤p C 이면 A ≤p C.

증명은 두 다항 환원 함수의 합성이 다시 다항이라는 사실에서 곧장 따라온다. 결과적으로 어떤 새 문제 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, … 줄줄이 사탕이 풀린다. 첫 번째 도미노만 쓰러뜨리면 나머지는 거저였다.

이것이 NP-완전성이 알고리즘 설계자에게 주는 “나쁜 소식의 좋은 면”이다. 어떤 새 문제가 어려워 보이면, 그것을 직접 다항 시간으로 풀려 애쓰지 말고 알려진 NP-완전 문제로부터 환원이 가능한지 살핀다. 환원이 성공하면 그 문제는 NP-완전이고, 적어도 “괜히 시간 낭비한 게 아니었다”는 면죄부를 얻는다.

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

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

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

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