NP-Complete — NP에서 가장 어려운 문제들

NP에 속하면서도 NP의 모든 문제를 자신으로 귀착시킬 수 있는 문제가 존재한다. 이런 문제를 NP-Complete라 부른다. 1971년 Stephen Cook이 SAT(Boolean Satisfiability) 문제가 NP-Complete임을 최초로 증명했다. 이 발견은 수천 개의 NP-Complete 문제 발견으로 이어졌다.

앞선 글에서 NP를 두 가지 동치 정의(NTM 기반, 검증자 기반)로 살펴봤다. 이 글에서는 NP 안에서도 특별한 위치를 차지하는 NP-Complete를 다룬다. NP-Complete는 “NP 문제 중 가장 어려운 것들”이다. 하나의 NP-Complete 문제를 다항식 시간에 풀 수 있다면, 모든 NP 문제를 다항식 시간에 풀 수 있다 — 즉 P = NP가 성립한다.

---

NP-Complete의 정의

두 번째 조건만 만족하고 NP에 속하지 않을 수 있는 문제들을 NP-Hard 라 한다. 따라서 NP-Complete = NP ∩ NP-Hard다.

---

Reduction (귀착)

Reduction(귀착) 은 문제의 난이도를 비교하는 핵심 도구다. 문제 $A$를 문제 $B$로 다항식 시간 귀착 한다는 것은, 다항식 시간에 계산 가능한 변환 함수 $f$가 존재해 다음이 성립하는 것이다.

$$A \leq_p B \iff \exists f \text{ (다항식 시간 계산 가능) s.t. } x \in A \Leftrightarrow f(x) \in B$$

귀착 과정은 다음 세 단계로 이루어진다.

1. 문제 $A$의 입력 $x$를 문제 $B$의 입력 $f(x)$로 변환(Transform) 한다.
2. $B$의 알고리즘으로 $f(x)$에 대한 답을 구한다.
3. 그 답이 $A$에 대한 답이 된다.

귀착과 난이도의 관계

$A \leq_p B$가 성립하면 “$B$는 적어도 $A$만큼 어렵다” — $B$를 풀 수 있으면 $A$도 풀 수 있다.

귀착 방향	의미
$A \leq_p B$	$B$의 난이도 $\geq$ $A$의 난이도
$A \leq_p B$ 이고 $B \leq_p A$	$A$와 $B$의 난이도가 동일

왜 다항식 시간으로 제한하는가? 변환에 너무 많은 계산을 허용하면, 변환 과정에서 문제를 거의 풀어버리게 되어 난이도 비교가 의미 없어진다. NP에서 “다항식 시간 귀착”은 원래 난이도를 왜곡하지 않는 변환을 의미한다.

---

SAT (Boolean Satisfiability)

SAT는 주어진 Boolean formula를 참(True)으로 만드는 변수 배정이 존재하는지 판별하는 문제다.

Satisfiable 예시:

$$\varphi = (p \lor q) \land \lnot p$$

$p = \text{False},\ q = \text{True}$로 설정하면 $\varphi$가 참 → Satisfiable

Unsatisfiable 예시:

$$\varphi = p \land \lnot p$$

어떤 변수 배정으로도 참이 될 수 없음 → Unsatisfiable

변수가 $n$개일 때 가장 단순한 방법은 $2^n$가지 배정을 모두 검사하는 것이다. 이보다 본질적으로 빠른 결정론적 다항식 시간 알고리즘은 아직 알려져 있지 않다.

---

Cook의 정리: SAT ∈ NP-Complete

SAT가 NP-Complete임을 증명하려면 두 조건을 모두 확인해야 한다.

1. SAT ∈ NP

NTM으로 모든 변수 배정을 비결정론적으로 탐색한다. 어떤 경로에서든 “Yes”인 배정을 찾으면 accept하므로, SAT ∈ NP.

2. 모든 NP 문제는 SAT로 귀착된다

이것이 Cook의 핵심 증명이다. 임의의 NP 문제 $L$에 대해 $L \leq_p \text{SAT}$를 보인다.

Step 1: 실행 전체를 계산표 한 장으로

$M$이 다항식 시간 $p(n)$ 안에 멈춘다고 하자. 그러면 헤드가 방문하는 테이프 칸도 $p(n)$개를 넘지 못한다. 시각을 세로로, 테이프 칸을 가로로 두면 $p(n) \times p(n)$짜리 표 한 장이 나온다. 이것을 계산표(tableau) 라 한다.

$i$행 $j$열 칸에는 시각 $i$에 테이프 $j$번 칸이 어떤 모습인지를 적는다. 칸이 가질 수 있는 값은 테이프 기호이거나, “여기 헤드가 있고 상태는 $q$다”를 뜻하는 기호다. 값의 가짓수 $|C|$가 $n$과 무관한 상수이므로, 칸마다 불리언 변수를 $|C|$개 두어 다음과 같이 인코딩한다.

$$x_{i,j,s} = \text{참} \iff i \text{행 } j \text{열의 값이 } s$$

변수는 모두 $|C| \cdot p(n)^2 = O(p(n)^2)$개다.

Step 2: “올바른 실행”을 네 가지 제약으로

표가 $M$의 accept하는 실행을 적은 것인지는 다음 넷을 모두 만족하는지로 판정된다.

제약	내용	크기
$\varphi_{\text{cell}}$	모든 칸이 값을 정확히 하나 갖는다	$O(p(n)^2)$
$\varphi_{\text{start}}$	첫 행이 입력 $x$에 대한 초기 구성이다	$O(p(n))$
$\varphi_{\text{move}}$	한 행에서 다음 행으로 넘어가는 것이 $M$의 전이 규칙을 따른다	$O(p(n)^2)$
$\varphi_{\text{accept}}$	어느 칸엔가 accept 상태가 나타난다	$O(p(n)^2)$

여기서 $\varphi_{\text{move}}$가 관건이다. “표 전체가 올바른 실행인가”를 한 번에 따지면 식이 걷잡을 수 없이 커진다.

Step 3: Choice는 어디에 있는가

DTM이라면 첫 행이 정해지는 순간 나머지 행이 모두 결정된다. NTM은 다르다. $\varphi_{\text{move}}$는 전이 규칙에 맞는 창을 모두 허용하므로, 한 행에서 다음 행으로 가는 길이 여럿일 수 있다. 논리식을 참으로 만드는 배정을 고르는 일이 곧 매 단계의 전이를 고르는 일이다.

구분	DTM	NTM
매 단계의 전이	하나로 정해짐	여럿 중 하나를 고름
시각 $t$의 구성(configuration)	입력 $x$가 정하면 하나로 결정	어느 전이를 골랐느냐에 따라 달라짐
표를 채우는 자유도	없음	있음 — 이 자유도가 곧 Choice

즉 Choice는 따로 붙이는 변수가 아니라 표를 채우는 자유도 자체다. 입력 $x$가 accept되는 경로가 존재한다면, 그 경로를 적은 표가 네 제약을 모두 만족한다. 거꾸로 네 제약을 만족하는 표는 accept로 끝나는 실행 하나를 그대로 적어 놓은 것이다.

$$x \in L \iff \varphi_x = \varphi_{\text{cell}} \land \varphi_{\text{start}} \land \varphi_{\text{move}} \land \varphi_{\text{accept}} \text{ 가 satisfiable}$$

식의 크기가 $O(p(n)^2)$이고 $x$를 보고 식을 적어 내는 데도 그만큼의 시간이면 충분하다. 변환이 다항식 시간에 계산 가능하므로 귀착의 조건이 갖춰졌다. 따라서 SAT ∈ NP-Complete.

회로를 거치면 무엇이 걸리는가. “실행을 회로로 바꾸고 회로를 논리식으로 바꾼다”는 설명도 흔하다. 다만 회로를 그대로 논리식으로 펼치면, 출력이 여러 곳에 쓰이는 게이트가 쓰인 횟수만큼 복제되어 식이 지수적으로 커질 수 있다. 이를 피하려면 게이트마다 새 변수를 하나씩 두고 “이 변수는 이 게이트의 출력과 같다”는 절을 더하는 방식(Tseitin 변환)이 필요하다. 크기는 선형으로 유지되지만 원래 식과 동치가 아니라 동시 충족 가능(equisatisfiable) 한 다른 식이 된다. 위 계산표 경로는 처음부터 논리식을 만들기 때문에 이 단계를 거치지 않는다.

---

NP-Hard

NP-Hard는 두 번째 조건(NP-hardness)만 만족하는 더 넓은 개념이다. NP-Complete와 달리, NP에 속하지 않을 수 있다.

	NP 포함	NP-hardness	예시
NP-Complete	✓	✓	SAT, 3-SAT, Vertex Cover
NP-Hard (NP 외부)	✗	✓	Halting Problem, TSP 최적화

최적화 문제 도 NP-Hard에 들어간다. 다만 최적화라는 형식 때문이 아니라, 밑에 깔린 판정 문제가 NP-Complete일 때 그렇다. TSP를 보자. “길이 $k$ 이하인 순회가 있는가”는 판정 문제이고 NP-Complete다. “가장 짧은 순회의 길이는 얼마인가”는 Yes/No가 아니라 수를 내놓으므로 NP에 속한다고 말할 수 없지만, 최적값을 한 번 부르면 $k$와 비교해 판정 문제의 답이 바로 나온다. NP-hardness는 이렇게 그대로 물려받는다.

아무 최적화 문제나 어려운 것은 아니다. 최단 경로를 예로 들면, 판정 버전인 “길이 $k$ 이하인 경로가 있는가”는 P에 속하고 최적값 자체도 Dijkstra로 다항식 시간에 구한다. 최적화 버전이라고 해서 NP-Hard가 되지는 않는다. 어려움을 만드는 것은 형식이 아니라 밑에 깔린 판정 문제다.

---

Co-NP

Co-NP는 NP의 보완(complement) 개념이다.

$$L \in \text{Co-NP} \iff L^c \in \text{NP}$$

NP가 “Yes”에 대한 짧은 증명서 가 존재하는 언어라면, Co-NP는 “No”에 대한 짧은 증명서 가 존재하는 언어다.

$\text{NP} \cap \text{Co-NP}$에 속하는 문제는 “Yes”와 “No” 모두에 대한 효율적인 증명이 존재한다. 대표적인 예로 소인수분해의 결정 버전(Factoring decision version) 이 있다.

NP = Co-NP인지는 아직 미해결 문제다. $P$는 여집합에 대해 닫혀 있으므로 $P = \text{NP}$가 성립하면 $\text{NP} = \text{Co-NP}$도 따라 나온다. 거꾸로 $\text{NP} = \text{Co-NP}$에서 $P = \text{NP}$가 따라 나오는지는 알려져 있지 않다. 성립하지 않는다고 밝혀진 것이 아니라, 어느 쪽인지 모른다.

---

결론