NP-완전 이해하기 (NP-Completeness)

Photo by Ryoji Iwata on Unsplash

지난번에 이어 이번에도 컴퓨터 과학의 최대 난제인 P vs NP에 대해서 좀더 깊게 들어가 보겠습니다. 이전 포스트에서는 P와 NP가 각각 직관적으로 어떤 의미를 갖고 있는지에 대해서 알아 보았는데요. 이를 보다 엄밀히 정의하면 다음과 같습니다.

• P는 다항 시간(polynomial time)에 결정론적(deterministically)으로 해결 가능한(solvable) 문제들의 집합입니다. 다시 말해, 어떤 결정 문제(decision problem) $X$에 대해, 주어지는 입력(input)이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 $X\in \mathrm{P}$입니다.
• NP는 다항 시간에 비결정론적(nondeterministically)으로 해결 가능한 문제들의 집합으로, 어떤 결정 문제 $X$에 대해, 주어지는 입력이 참인지 거짓인지를 다항 시간에 비결정론적으로 해결하는 알고리즘이 존재하면 $X\in \mathrm{NP}$입니다.
• NP의 또 다른 정의는 다항 시간에 결정론적으로 검증 가능한(verifiable) 문제들의 집합입니다. 자세히 살펴보자면, 어떤 결정 문제 $X$에 대해 어떤 입력과 입력 크기의 어떤 다항식으로 표현되는 크기를 갖는 증거(certificate)를 함께 제공 받았을 때 이를 다항 시간에 결정론적으로 검증하는 알고리즘이 존재하면 $X\in \mathrm{NP}$입니다.

해당 글에서는 계산 이론(theory of computation)에 대한 배경 지식 없이도 이해할 수 있도록 위 내용을 최대한 가볍게 소개하였습니다. 약간 엄밀하지 못한 부분이 있을 수는 있으나 나름 필요한 부분은 모두 충족했다고 생각합니다. 궁금하신 분들은 아래를 참조하세요.

2020/09/08 - [수학적 도구/Theory of computation] - P vs NP 쉽게 이해하기

P vs NP 쉽게 이해하기

위 정의에 따르면 $\mathrm{P}\subseteq \mathrm{NP}$는 쉽게 알 수 있습니다. 궁금한 것은 $\mathrm{P}=\mathrm{NP}$인지, 아니면 $\mathrm{P}⊊\mathrm{NP}$인지 입니다. 둘 중에 어느 것이 사실인지를 밝히고 엄밀히 증명하는 것이 바로 P vs NP 문제입니다.

 

이 문제를 어렵게 만드는 원인 중 하나는 P와 NP에 속하는 문제가 무수히 많다는 점입니다. 우리가 어떤 두 집합 $A,B$에 대해 $A=B$를 증명하기 위해서는 $A\subseteq B$임과 $B\subseteq A$임을 보이면 됩니다. 그러려면 모든 $a\in A$에 대해 $a\in B$임을 증명하고, 모든 $b\in B$에 대해서도 $b\in A$임을 증명하면 됩니다. 하지만 만약 $A,B$의 원소의 개수가 무한하면 어떻게 될까요? 그렇다면 앞에서처럼 하나씩 비교하는 것은 불가능합니다. 대신 각 집합의 원소가 공통적으로 갖는 특징을 규명하고 이를 활용하여 증명해야 합니다.

 

이미 우리는 $\mathrm{P}\subseteq \mathrm{NP}$임을 압니다. 문제는 반대 방향이죠. 따라서 지난 수십년간 많은 수학자들과 컴퓨터 과학자들은 NP의 문제들이 갖는 특징을 규명하기 위해 많은 노력을 기울였습니다. 그 결과, 어떤 특정 문제들은 그 자체로 NP에 속하기도 하지만 다른 모든 NP의 문제들에 비해 "어렵다"는 것을 보일 수 있었죠. 또한 그 문제들 중 아무 하나만 P에 속한다는 것을 보인다면 $\mathrm{P}=\mathrm{NP}$라고 결론을 내릴 수 있다는 것을 알게 됩니다. (반대로 P에 속하지 않는다는 것을 보인다면, 그 자체로 이미 $\mathrm{P}⊊\mathrm{NP}$임을 보이는 것입니다.)

 

이번 시간에는 위 성질을 만족하는 NP의 문제들이 어떤 것인지에 대해서 알아 보겠습니다. 글은 다음과 같이 구성되어 있습니다.

• 다항 시간 환산 가능성(polynomial-time reducibility)
• NP-난해와 NP-완전(NP-hardness and NP-completeness)
• NP-난해 증명 방법

번역은 위키피디아를 참조하였습니다.^[3]

다항 시간 환산 가능성(Polynomial-Time Reducibility)

어떤 문제가 다른 문제보다 어렵다, 혹은 쉽지 않다는 것은 무슨 의미일까요? 이해를 위해 예시를 들어 보겠습니다. 우리에게 서로 다른 두 문제 $X$와 $Y$가 주어졌다고 가정해 봅시다. 우리는 $Y$를 해결하는 방법은 알고 있지만, $X$를 해결하는 방법은 모릅니다. 그런데 만약 우리가

• $X$의 임의의 입력을 잘 수정하면 적절한 $Y$의 입력을 만들 수 있고,
• 반대로 만들어진 $Y$의 입력을 이미 아는 방법을 이용하여 해결한 결과를 잘 조정하면 원래 $X$의 입력의 적절한 결과를 복원할 수 있다면,

우리는 $X$를 해결하는 방법을 만들 수 있습니다. 이 기법을 우리는 환산(reduction)이라고 부릅니다. 환산은 알고리즘 전반에 걸쳐서 요긴하게 사용됩니다. 한 가지 유명한 예시는 최대 이분 매칭 문제(maximum bipartite matching problem)를 최대 흐름 문제(maximum flow problem)로 환원하여 해결하는 것입니다. 그 방법은 제 초창기 글에서도 다룬 적이 있습니다.

2019/01/28 - [조합론적 최적화/Matching] - 홀의 정리 (Hall's Theorem)

홀의 정리 (Hall's Theorem)

우리의 목표는 "가장 어려운" NP 문제를 찾는 것입니다. 그러므로 그 문제가 가져야 하는 성질은 분명 모든 NP 문제를 그 문제로 환산하여 해결할 수 있어야 한다는 것입니다. 더구나 그 문제도 NP에 속하기를 원하므로 환산 과정에 시간이 너무 많이 들어가서도 안 됩니다. 이는 다음 정의를 통해서 정형화됩니다.

정의 1. 다항 시간 환산 가능성^[ㄱ]

---

어떤 두 결정 문제 $X$와 $Y$에 대해, 만약 아래를 만족하면서 $X$의 입력 집합에서 $Y$의 입력 집합으로 가는 (결정론적으로) 다항 시간에 연산이 가능한(polynomial-time computable) 함수 $f$가 존재한다면, 우리는 $X$를 $Y$로 다항 시간 환산 가능(polynomial-time reducible)하다고 말하며, 기호로는 $X{\le }_{P}Y$로 표현한다.

• 임의의 $X$의 입력 $x$에 대해, $x$가 $X$에서 참인 필요충분조건은 $f(x)$가 $Y$에서 참인 것이다.

그림 1. 정의 1의 조건을 만족하는 $f$에 대한 도식. 좌측은 결정 문제 $X$의 입력 집합을, 우측은 $Y$의 입력 집합을 나타낸다. $x_1$이 $X$에서 참이면 $f(x_1)$도 $Y$에서 참이며, $x_2$가 거짓이면 $f(x_2)$도 거짓이어야 한다. $f(x)$의 형태로 표현되는 $Y$의 입력에 대해서만 참/거짓 여부를 따지는 것으로 충분하다.(초록색 배경)

여기서 중요한 점은 이 정의에서 $Y$의 모든 입력에 대한 정보를 알 필요가 없다는 것입니다. $X$의 입력 $x$에 의해 정의되는 특정한 입력 $f(x)$가 $Y$에서 참인지 거짓인지만 알면 충분합니다. 게다가 $Y$를 어떻게 해결할지도 중요하지 않습니다. 만약 $x$가 참이면 $f(x)$도 참이고, 반대로 $x$가 거짓이면 $f(x)$도 거짓이 된다는 사실을 증명하는 것으로 끝납니다. 아, 물론 $f$는 다항 시간에 결정론적으로 연산이 되어야 하고요.

NP-난해와 NP-완전(NP-Hardness & NP-Completeness)

이제 우리는 "가장 어려운" NP 문제를 엄밀히 정의할 수 있습니다. 먼저 다음 정의는 NP에 속하는 모든 문제보다 어렵다는 것을 나타냅니다.

정의 2. NP-난해

---

어떤 결정 문제 $Y$에 대해 NP에 속하는 임의의 문제 $X$가 $Y$로 다항 시간 환산 가능하면, 즉 $\mathrm{\forall }X\in \mathrm{NP},X{\le }_{P}Y$를 만족하면 $Y$를 NP-난해(NP-hard)하다고 말한다.

그러면 "가장 어려운" NP 문제는 다음과 같이 정의됩니다.

정의 3. NP-완전

---

어떤 결정 문제 $Y$가 NP에 속하면서 NP-난해하면, 우리는 $Y$가 NP-완전(NP-complete)하다고 부른다.

서론에서 우리는 NP에 속하는 모든 문제보다 어려운 문제가 만약 다항 시간에 결정론적으로 해결된다면 우리는 $\mathrm{P}=\mathrm{NP}$임을 보일 수 있을 것이라고 했습니다. 다음 정리는 이를 보다 구체적으로 나타냅니다.

정리 1. NP-난해 문제의 성질

---

어떤 NP-난해한 결정 문제 $Y$에 대해, 이를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면, 즉 $Y\in \mathrm{P}$이면, $\mathrm{P}=\mathrm{NP}$이다.

[증명] 정의에 의해 임의의 $X\in \mathrm{NP}$에 대해 $X{\le }_{P}Y$입니다. 그러므로 정의 1의 조건을 만족하는 다항 시간에 연산 가능한 함수 $f$가 존재합니다. $Y$를 다항 시간에 해결하는 알고리즘을 $\mathcal{B}$라고 하겠습니다. 그러면 우리는 $X$를 다항 시간에 결정론적으로 해결하는 알고리즘 $\mathcal{A}$를 만들 수 있습니다. 방법은 간단합니다. 임의의 입력 $x$에 대해, 먼저 $f(x)$를 계산한 후, $\mathcal{B}$에 $f(x)$를 넣어서 결과를 얻습니다. 만약 $\mathcal{B}$가 참을 출력하면 $\mathcal{A}$도 따라서 참을 출력하고 거짓이라고 하면 거짓을 반환합니다.

그림 2. $X$를 다항 시간에 결정론적으로 해결하는 $\mathcal{A}$의 모습.

$\mathcal{A}$가 올바르게 동작한다는 것은 보이겠습니다. 만약 $x$가 $X$에서 참이라면, $f$의 성질에 의해 $f(x)$도 $Y$에서 참입니다. $\mathcal{B}$는 올바른 알고리즘이므로 $f(x)$가 입력되었을 때 분명 참을 반환했을 것입니다. 따라서 $\mathcal{A}$도 참을 반환합니다. 반대로 $x$가 $X$에서 거짓인 경우에는 $f(x)$도 $Y$에서 분명 거짓이었을 것이므로 위 논의를 그대로 따라가면 $\mathcal{A}$가 거짓을 반환한다는 것을 보일 수 있습니다. 마지막으로, $\mathcal{B}$, $f$ 모두 다항 시간에 결정론적으로 동작하므로 $\mathcal{A}$가 다항 시간에 결정론적으로 동작한다는 것도 쉽게 이끌어낼 수 있습니다. 이것으로 $X\in \mathrm{P}$를 이끌어낼 수 잇습니다. ■

 

위에서 중요한 점은 증명의 어느 곳에서도 비결정론적 알고리즘에 의거하지 않았다는 것입니다. 이는 "난해"의 개념이 두 문제가 주어졌을 때 어느 문제가 풀기 쉽고 어느 문제가 풀기 어려운지를 따지는 데에만 있기 때문입니다. 다시 말해, 어떤 문제가 NP-난해하다는 것은 임의의 NP 문제를 해당 문제로 (다항 시간에) 환산하여 해결할 수 있다는 것만 나타내며, 해당 문제가 어떤 방식으로 해결되는지에 대한 정보는 전혀 담고 있지 않습니다. 추가적으로 우리가 만약 해당 문제를 비결정론적 알고리즘으로 다항 시간에 해결할 수 있다는 사실을 안다면, 이는 NP에 속하게 되고 따라서 NP-완전하다는 것을 알게 됩니다.

 

개인적으로도 처음에는 이 개념들이 익숙하지 않아서 이해하는데 애를 먹었습니다. 하지만 각 개념이 무엇을 표현하는지를 곰곰이 따져 본다면 생각보다 그리 어려운 개념을 표현하고 있지는 않다는 사실을 발견하시리라 생각합니다.

NP-난해 증명 방법

어떤 문제가 NP에 속하는 것을 보이는 것은 어렵지 않습니다. 해당 문제를 다항 시간에 비결정론적으로 해결하는 알고리즘을 아무거나 하나 제시하면 되기 때문이죠. 반대로 어느 문제가 NP-난해함을 보이는 것은 일견 쉬워 보이지는 않습니다. 정의 상 NP에 속하는 모든 문제로부터 그 문제로 다항 시간 환산 가능함을 보여야 하기 때문이죠. 정의의 조건을 만족하는 함수 $f$를 만드는 것은 차치하더라도 상상할 수 있는 모든 NP 문제를 상정하는 것 자체가 이미 증명을 어렵게 만듭니다.

 

이를 보다 쉽게 할 수 있는 방법은 없을까요? 다행스럽게도 만약 어떤 문제가 이미 NP-난해하다는 것을 알고 있다면 이를 활용하여 다른 문제의 NP-난해성을 보일 수 있습니다.

정리 2. NP-난해 문제 증명 방법

---

어떤 NP-난해 문제 $X$에 대하여, 만약 어떤 다른 문제 $Y$가 $X{\le }_{P}Y$를 만족한다면, $Y$는 NP-난해하다.

[증명] 증명의 목표는 임의의 $Z\in \mathrm{NP}$에 대해, $Z{\le }_{P}Y$를 보이는 것입니다. 먼저 $X$는 NP-난해하므로 $Z{\le }_{P}X$를 만족합니다. 따라서 $Z$의 아무 입력 $z$에 대해,

$$z\text{ is true in }Z\iff f(z)\text{ is true in }X$$

를 만족하는 다항 시간에 연산 가능한 함수 $f$가 존재합니다. 게다가 우리는 $X{\le }_{P}Y$라고 하였으므로, $X$의 아무 입력 $x$에 대해,

$$x\text{ is true in }X\iff g(x)\text{ is true in }Y$$

를 만족하는 다항 시간에 연산 가능한 함수 $g$도 존재하죠. 따라서 이 둘을 합성하면 우리는

$$z\text{ is true in }Z\iff g\circ f(x)=g(f(x))\text{ is true in }Y$$

를 만족하는 것을 알 수 있습니다. $f$와 $g$ 모두 다항 시간에 연산이 가능하므로 $g\circ f$도 다항 시간에 연산할 수 있습니다. 따라서 $g\circ f$가 정의 1의 조건을 만족하므로 이것으로 증명이 완료됩니다. ■

예제: 3-SAT ${\le }_P$ Independent Set

위에서 공부한 내용을 실제 예시에 적용해 보도록 하겠습니다. 먼저 문제들을 소개하겠습니다. 첫 번째는 3-충족 가능성 문제(3-satisfiability problem, 3-SAT)입니다. 이 문제는 NP-완전한 문제를 공부할 때 가장 먼저 배우는 문제로, 그 정의는 다음과 같습니다. 이 문제의 입력은 다음 두 가지로 구성됩니다.

• 변수(variable)의 개수 $n$ : 각 변수 $x_1,\cdots ,x_n$은 참 또는 거짓을 할당 받을 수 있습니다. $x_i$의 논리 부정(NOT)은 $\overline{x_i}$로 표현됩니다. 이때, $x_1,\cdots ,x_n$과 $\overline{x_1},\cdots ,\overline{x_n}$을 리터럴(literal)이라고 부릅니다.
• 절(clause) $C_1,\cdots ,C_m$ : 각 절은 정확히 세 리터럴의 논리합(OR, $\vee$)으로 연결되어 있습니다.

만약 $x_1,\cdots ,x_n$에 참/거짓을 적절히 할당하여 모든 $C_1,\cdots ,C_m$을 참으로 만드는 방법이 존재하면 해당 입력은 이 문제에서 참이 됩니다. 반대로 그러한 할당이 존재하지 않으면 해당 입력은 거짓이 됩니다.

 

예를 들어, 입력이 다음과 같이 $n=3$이고

$$\begin{array}{}\text{(1)}& C_1=\overline{x_1}\vee \overline{x_2}\vee \overline{x_3},C_2=x_1\vee x_2\vee \overline{x_3},C_3=x_1\vee \overline{x_2}\vee x_3{C}_4=\overline{x_1}\vee x_2\vee \overline{x_3}\end{array}$$

일 때, 우리는 $(x_1,x_2,x_3)=(\mathsf{false},\mathsf{true},\mathsf{true})$로 할당하여 $C_1,\cdots ,C_4$를 모두 참으로 만들 수 있으므로 이 입력은 참입니다. 반면, $n=2$이고

$$C_1=x_1\vee x_1\vee x_2,C_2=x_1\vee \overline{x_2}\vee \overline{x_2},C_3=\overline{x_1}\vee x_2\vee x_2{C}_4=\overline{x_1}\vee \overline{x_1}\vee \overline{x_2}$$

인 입력은 $(x_1,x_2)$를 어떻게 할당하든지 간에 $C_1,\cdots ,C_4$를 모두 참이 되게 만드는 방법은 없으므로 거짓이 됩니다.

 

다음은 유명한 그래프 문제 중 하나인 독립 집합 문제(independent set problem)입니다. 이 문제도 다음 두 가지가 입력으로 주어집니다.

• 가중치도 없고 방향도 없는(unweighted undirected) 그래프 $G=(V,E)$
• 목표 크기 정수 $k$

$G$에서의 독립 집합 $S\subseteq V$는 서로 인접하지 않은 정점의 집합을 의미합니다. 다시 말해, 어떤 $v\in V$가 $S$에 속해 있으면, $v$에 인접한(adjacent) 정점은 $S$에 들어있으면 안 됩니다. 문제의 목표는 $G$에 크기가 $k$보다 크거나 같은 독립 집합이 존재하는지를 판단하는 것입니다.

그림 3. 독립 집합의 예시. 위 그래프 $G$에는 크기가 3인 독립 집합이 존재한다. 하지만 크기가 5 이상인 독립 집합은 존재하지 않는다. 따라서 $⟨G,3⟩$은 참이나, $⟨G,5⟩$는 거짓이다.

한눈에 보기에 서로 관련이 없을 것 같은 두 문제가 사실은 매우 밀접한 관련이 있습니다. 바로 3-SAT이 독립 집합 문제로 다항 시간 환산 가능하다는 점입니다. 다시 말해, 우리가 만약 독립 집합 문제를 다항 시간에 결정론적으로 해결하는 방법을 알고 있다면, 분명 우리는 3-SAT도 다항 시간에 결정론적으로 해결할 수 있다는 뜻이죠.

정리 3. 3-SAT과 독립 집합 문제의 관계

---

3-SAT ${\le }_P$ Independent Set

[증명] 정의 1의 조건을 만족하는 3-SAT의 입력을 입력받아 독립 집합 문제의 입력을 출력하는 다항 시간에 연산이 가능한 함수 $f$를 하나 제시하면 증명이 완성됩니다. 다음의 $f$를 고려하겠습니다. 3-SAT의 입력을 $⟨n,C_1,\cdots ,C_m⟩$이라고 하고, 각 $C_j$는 ${\ell }_{j1}\vee {\ell }_{j2}\vee {\ell }_{j3}$의 리터럴을 갖는다고 하겠습니다.

 

위 입력에 대해, 그래프 $H=(V,E)$를 다음과 같이 정의합니다.

• 정점 집합 $V$는 모든 절의 리터럴에 대응합니다. 즉, $$V:=\{{\ell }_{j1},{\ell }_{j2},{\ell }_{j3}:j=1,\cdots ,m\}$$입니다. 참고로 $|V|=3m$입니다.
• 간선 집합 $E$는 $E_1\cup E_2$로 구성됩니다. 첫 번째 $E_1$은 각 절에 해당하는 정점을 모두 연결하는 것으로 $$E_1:=\{({\ell }_{j1},{\ell }_{j2}),({\ell }_{j2},{\ell }_{j3}),({\ell }_{j3},{\ell }_{j1}):j=1,\cdots ,m\}$$으로 표현할 수 있습니다. 두 번째 $E_2$는 서로 다른 절에 속한 두 리터럴이 서로 논리 부정 관계를 이루면 연결해 줍니다. 다시 말해, $$E_2:=\{({\ell }_{ji},{\ell }_{j^{\prime }{i}^{\prime }}):j\ne j^{\prime }\text{ and }{\ell }_{ji}=\overline{{\ell }_{j^{\prime }{i}^{\prime }}}\}$$과 같습니다. 참고로 $H$는 단순 그래프(simple graph)이므로 $|E|\le \frac{|V{|}^2}{2}=4.5m^2$을 만족합니다.

이제 함수 $f$를 $f(⟨n,C_1,\cdots ,C_m⟩)=⟨H,m⟩$으로 정의하겠습니다. 다시 말하면, $⟨n,C_1,\cdots ,C_m⟩$의 3-SAT 입력을 $f$에 넣으면 그래프 $H$에서 크기가 $m$ 이상인 독립 집합을 찾는 것으로 환산한다는 뜻입니다.

그림 4. 3-SAT 입력 (1)을 $f$로 연산하여 얻은 독립 집합 문제 입력. 겹선으로 표현된 간선이 $E_1$, 홑선으로 표현된 간선이 $E_2$를 나타낸다.

과연 $f$는 정의 1의 조건을 만족할까요? 먼저 $⟨n,C_1,\cdots ,C_m⟩$에서 $C_1,\cdots ,C_m$을 모두 참으로 만드는 $x_1,\cdots ,x_n$의 할당이 존재한다고(즉, 3-SAT에서 참인 입력이라고) 가정하겠습니다. 그러면 분명 각 $C_j$에는 참인 리터럴이 최소한 하나씩은 존재합니다. 일반성을 잃지 않고, ${\ell }_{j1}$이 모두 참이라고 가정하겠습니다. 그러면 $S:=\{{\ell }_{11},\cdots ,{\ell }_{m1}\}$는 $H$에서 크기가 $m$인 독립 집합이 됩니다. 그 이유는 쉽게 알 수 있습니다. $H$에서 각 절의 리터럴에 해당하는 정점 ${\ell }_{j1},{\ell }_{j2},{\ell }_{j3}$에서 정확히 하나씩만 뽑았으므로 $S$는 $E_1$에 의해서 인접하지 않을 것이고, 어떤 리터럴 ${\ell }_{ji}$가 참이면 $\overline{{\ell }_{ji}}$은 거짓이므로, $E_2$에 의해서 인접한 정점들도 $S$에는 없기 때문입니다. 그러므로 $⟨H,m⟩$은 참인 독립 집합 문제 입력입니다.

 

반대로 $H$에 크기가 $m$ 이상인 독립 집합 $S^{\prime }$이 존재한다고 가정하겠습니다. 우선 ${\ell }_{j1},{\ell }_{j2},{\ell }_{j3}$는 서로 인접하므로 독립 집합의 성질에 의해 이 중에는 최대 한 개만 $S^{\prime }$에 들어갈 수 있습니다. $S^{\prime }$의 크기가 $m$ 이상이라고 하였으므로 이는 분명 각 $C_j$의 리터럴에 대응하는 정점 중에서 정확히 하나씩 $S^{\prime }$에 뽑혔다는 것을 의미합니다. 일반성을 잃지 않고 각각 ${\ell }_{j1}$이 $S^{\prime }$에 뽑혔다고 가정하겠습니다. 만약 어떤 서로 다른 두 ${\ell }_{j1},{\ell }_{j^{\prime }1}$이 논리 부정 관계였으면 $E_2$에 의해서 둘 중 하나는 $S^{\prime }$에 뽑히지 말았어야 합니다. 그러므로 우리는 ${\ell }_{11},\cdots ,{\ell }_{m1}$을 모두 참으로 만들 수 있는 $(x_1,\cdots ,x_n)$의 할당이 존재한다는 것을 알 수 있습니다. 따라서 $⟨n,C_1,\cdots ,C_m⟩$은 참인 3-SAT 입력입니다. 이것으로 $f$가 정의 1의 조건을 만족한다는 것을 보였습니다.

그림 5. 그림 4에서 크기가 $m=4$ 이상인 독립 집합의 예시. 이는 $(x_1,x_2,x_3)=(\mathsf{false},\mathsf{true},\mathsf{true})$에 대응한다.

마지막으로 남은 것은 $f$가 다항 시간에 연산이 가능하냐는 것입니다. $⟨n,C_1,\cdots ,C_m⟩$은 $O(\log n+m)$ 비트(bit)로 표현이 가능합니다. 앞에서 $|V|=3m,|E|\le 4.5m^2$임을 보였으므로 $⟨H,m⟩$은 $O(m^2+\log m)=O(m^2)$ 비트로 표현이 가능합니다. 따라서 입력 크기의 제곱 시간에 연산이 가능함을 확인할 수 있습니다. ■

 

앞에서도 설명했지만, 위 증명에서 가장 중요한 부분은 독립 집합 문제의 모든 입력에 대해 참/거짓 여부를 알 필요가 없다는 점입니다. 대신 $f$를 통해 출력될 수 있는 꼴의 그래프(위에서는 $H$)에 대해서만 참/거짓 여부를 가정하면 됩니다. 이 부분이 처음 NP-난해 증명을 접할 때 많은 분들이 정확히 이해하지 못하는 부분이니 주의하시기 바랍니다.

마치며

이것으로 NP 문제들 중에서 "가장 어려운" 문제인 NP-완전한 문제들에 대해서 알아 보았습니다. 또, 어떤 문제의 NP-난해성은 다른 알려진 NP-난해한 문제를 해당 문제로 다항 시간 환산 가능함을 보이는 것으로 증명할 수 있다는 점도 공부하였습니다. 그 실례로 3-SAT을 독립 집합 문제로 다항 시간 환산 가능하다는 것을 보였습니다.

 

그러면 맨 처음에는 어떤 문제가 NP-난해하다고 알려졌을까요? 이를 모르면 우리는 정리 2를 써먹을 수 없습니다. 수학적 귀납법에서 기저 조건이 만족함을 보여야하는 것과 같은 이치지요. 따라서 분명 최소한 한 문제는 실제 임의의 NP 문제로부터 다항 시간 환산 가능하다는 것을 직접적으로 보여야 합니다. 그러한 기원 격의 문제가 바로 앞에서 본 3-SAT입니다.

정리 4. 쿡-레빈 정리(Cook-Levin theorem)^[ㄴ]

---

3-SAT은 NP-완전하다.

예전에 이 정리의 증명을 본 적이 있는데, 양이 상당하더군요. 나중에 기회가 되면 이를 다루어 보도록 하겠습니다.

 

궁금하신 점이 있으시거나, 글에 잘못된 내용이 있는 경우에는 알려주시기 바랍니다. 고맙습니다. :)

각주

[ㄱ] 다항 시간 환산 가능성을 정의하는 다른 방식이 있습니다. 우리가 어떤 문제 $Y$를 해결하는 알고리즘 $\mathcal{B}$를 안다고 가정했을 때 어떤 다른 문제 $X$를 $\mathcal{B}$를 다항 횟수 호출하고 그외의 작업도 모두 다항 시간에 수행하여 해결할 수 있다면, $X$를 $Y$로 다항 시간 환산 가능하다고 말합니다. 본문의 정의보다 덜 제한적인 이 정의는 쿡 환산(Cook reduction) 혹은 튜링 환산(Turing reduction)으로 불립니다.^[1] 반면 본문의 정의는 카프 환산(Karp reduction)이라고 불립니다.^[2]

 

[ㄴ] 쿡-레빈 정리는 사실 3-SAT이 아니라 그것의 일반화된 문제인 SAT이 NP-완전하다는 것입니다.^[1] SAT은 입력으로 주어지는 절에 사용되는 리터럴의 개수에 제한이 없는 문제입니다. 나중에 R. Karp가 SAT ${\le }_P$ 3-SAT임을 보이고, 따라서 정리 4가 성립합니다.^[2]

참조

[1] Stephen A. Cook "The complexity of theorem-proving procedures." In Proceedings of the third annual ACM symposium on Theory of computing, pp. 151-158. 1971.

 

[2] Richard M. Karp "Reducibility among combinatorial problems." In Complexity of computer computations, pp. 85-103. Springer, Boston, MA, 1972.

 

[3] https://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84