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} \subsetneq \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} \subsetneq \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 \leq_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\)로 다항 시간 환산 가능하면, 즉 \(\forall X \in \mathrm{NP}, X \leq_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 \leq_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 \leq_P Y \)를 만족한다면, \(Y\)는 NP-난해하다.

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

\[ z \text{ is true in } Z \Leftrightarrow f(z) \text{ is true in } X \]

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

\[ x \text{ is true in } X \Leftrightarrow g(x) \text{ is true in } Y \]

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

\[ z \text{ is true in } Z \Leftrightarrow g \circ f(x) = g(f(x)) \text{ is true in } Y \]

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

예제: 3-SAT \( \leq_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\)이고

\[ C_1 = \overline{x_1} \vee \overline{x_2} \vee \overline{x_3}, \quad C_2 = x_1 \vee x_2 \vee \overline{x_3}, \quad C_3 = x_1 \vee \overline{x_2} \vee x_3 \quad C_4 = \overline{x_1} \vee x_2 \vee \overline{x_3} \tag{1} \]

일 때, 우리는 \( (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, \quad C_2 = x_1 \vee \overline{x_2} \vee \overline{x_2}, \quad C_3 = \overline{x_1} \vee x_2 \vee x_2 \quad 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 이상인 독립 집합은 존재하지 않는다. 따라서 \( \langle G, 3 \rangle \)은 참이나, \( \langle G, 5 \rangle \)는 거짓이다.

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

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

---

3-SAT \( \leq_P \) Independent Set

[증명] 정의 1의 조건을 만족하는 3-SAT의 입력을 입력받아 독립 집합 문제의 입력을 출력하는 다항 시간에 연산이 가능한 함수 \(f\)를 하나 제시하면 증명이 완성됩니다. 다음의 \(f\)를 고려하겠습니다. 3-SAT의 입력을 \(\langle n, C_1, \cdots, C_m \rangle\)이라고 하고, 각 \(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'i'}) : j \neq j' \text{ and } \ell_{ji} = \overline{\ell_{j'i'}} \} \]과 같습니다. 참고로 \(H\)는 단순 그래프(simple graph)이므로 \( |E| \leq \frac{|V|^2}{2} = 4.5m^2 \)을 만족합니다.

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

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

과연 \(f\)는 정의 1의 조건을 만족할까요? 먼저 \(\langle n, C_1, \cdots, C_m \rangle\)에서 \(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\)에는 없기 때문입니다. 그러므로 \( \langle H, m \rangle \)은 참인 독립 집합 문제 입력입니다.

 

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

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

마지막으로 남은 것은 \(f\)가 다항 시간에 연산이 가능하냐는 것입니다. \( \langle n, C_1, \cdots, C_m \rangle \)은 \( O(\log n + m) \) 비트(bit)로 표현이 가능합니다. 앞에서 \( |V| = 3m, |E| \leq 4.5m^2 \)임을 보였으므로 \( \langle H, m \rangle \)은 \( 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 \(\leq_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