[계산이론] #12. Knapsack, Clique, 3SAT Problem
Running Time의 비교
$\textbf{P}$에 속하는 Language들은 전부 Polynomial Time에 해결 가능하기 때문에, 어떻게 보면 이들을 해결하기 "쉽다"고 말할 수 있습니다.
이렇게 어떤 Language가 얼마나 쉬운지는 이 Language의 Running Time에 의해 결정됩니다. 더 나아가서, 어떤 두 Language의 Running Time을 비교해서 어떤 Language가 더 쉬운지, 어려운지를 결정할 수 있습니다.
언어 $A$가 언어 $B$보다 쉬울 경우, 이를 $A\leq_{P}B$ 라고 표현합니다. 아랫첨자 $P$는 Running Time에서 Polynomial 한 변수는 무시하겠다는 의미로 붙인 것입니다. 이를 수학적으로 표현하자면,
두 언어 $A, B\subseteq \left\{0,1 \right\}^{*}$에 대해, 아래 조건을 만족하는 함수 $f:\left\{0,1 \right\}^{*}\rightarrow \left\{0,1 \right\}^*$가 존재할 경우 $A\leq_{P}B$ 라고 표현합니다.
- $f\in \textbf{FP}$ (Polynomial Time에 해결 가능한 함수의 집합)
- $\forall w\in \left\{0,1 \right\}^*, w\in A\Leftrightarrow f\left ( w \right )\in B$
위가 의미하는 것은 $w$가 $A$에 속하는지 판단하는 문제를, $f\left ( w \right )$가 $B$에 속하는지 판단하는 문제로 Polynomial Time에 바꿀 수 있는 어떤 함수 $f$가 존재한다는 것입니다. 이런 함수가 존재한다면 우리는 $A\leq_{P}B$라고 쓰고, B is at least as hard as A (B는 최소한 A보다는 어렵다), 혹은 A is Polynomial-Time Reducible to B (A는 Polynomial Time에 B로 변환될 수 있다) 라고 표현합니다.
그럼 당연하게도, $A\leq_{P}B$가 성립하며 $B$가 $\textbf{P}$에 속한다면, $A$ 역시 $\textbf{P}$에 속합니다.
이를 활용해서 아래 정리를 한번 보겠습니다.
$\textbf{P}$인 언어 $A$에 대해, $B\neq \phi ,B\neq \left\{0,1 \right\}^*$인 언어 $B$가 있다고 생각합시다. 그러면, 항상 $A\leq_{P}B$입니다. 다르게 말하면, $\textbf{P}$는 해결할 수 있는 가장 쉬운 Language라는 의미입니다.
이를 증명해보겠습니다. 임의로 $B$를 잡았다고 가정하고, $B$에 속하는 문자열 $u$와 속하지 않는 문자열 $v$를 하나씩 생각합시다. $B\neq \phi ,B\neq \left\{0,1 \right\}^*$라는 조건 때문에 $u, v$는 반드시 존재하겠죠. 이때, 아래와 같은 함수 $f:\left\{0,1 \right\}^{*}\rightarrow \left\{0,1 \right\}^*$를 정의합시다.
$$f\left ( w \right )=\left\{\begin{matrix}
u & if\;w\in A \\
v & if\;w \notin A \\
\end{matrix}\right.$$
그러면 $A$가 $\textbf{P}$ 에 속하므로, 이 함수 $f$는 $\textbf{FP}$에 속하게 됩니다. 위의 조건을 만족하는 함수 $f$가 존재하므로, 정의에 의해 $A\leq_{P}B$가 성립합니다.
Knapsack Problem (가방 채우기 문제)
이제부터 Knapsack이라 불리는 문제를 한번 풀어볼 겁니다. 가방에 물건을 채울 건데, 각 물건은 각자의 무게와 가치를 가집니다. 물건들의 리스트는 아래와 같이 표로 주어집니다.
1번 물체는 2의 무게와 1의 가치를, 2번 물체는 3의 무게와 9의 가치를 가지는 식입니다. 그리고 가방이 있습니다. 가방에는 최대로 넣을 수 있는 무게가 정해져 있습니다. 이 값을 $W$라고 정의합니다. 그리고, 이 가방에 담고 싶은 목표 가치도 존재합니다. 이 값을 $V$라고 정의합니다. 예시로, $W$의 값을 8, $V$의 값을 20이라고 하겠습니다.
저희의 목표는 최대 무게가 $W$를 넘지 않으면서 가치가 $V$ 이상이 되도록 가방에 물건을 채우는 것입니다. 어떤 물건들을 선택하면 이것이 가능할지 출력하는 것이 바로 Knapsack Problem이고요.
위 문제의 정답은 바로 2, 4입니다. 두 물건을 가방에 담게 되면 무게는 3+4인 7이 되고, 가치는 9+12인 21이 됩니다.
이제 아래와 같이 Language $KS$를 정의하겠습니다.
이제 잠시 $KS$는 제쳐두고, 이 전 글에서 다루었던 언어 $SOS$를 한번 떠올려보겠습니다.
구조가 비슷하다는 느낌이 드시죠? 이 $SOS$는 항상 $KS$보다 해결하기 쉽습니다. 즉, $SOS\leq_{P}KS$ 입니다. 이를 증명해 보도록 하겠습니다.
위를 증명하기 위해서 저희는 아래 조건을 만족하며 $\textbf{FP}$에 속하는 함수 $f$가 존재함을 보여야 합니다.
함수 $f$를 $f\left ( \left<a_1, \cdots, a_m, b \right> \right )=\left<a_1, \cdots, a_m, a_1, \cdots, a_m, b, b \right>$ 와 같이 정의하겠습니다. $\left<a_1, \cdots, a_m, b \right>$가 $SOS$의 원소이면 $\sum_{i=1}^{m}c_i a_i = b$인 $c_i$들의 쌍이 존재한다는 뜻입니다.
그런데, 이는 곧 $\sum_{i=1}^{m}c_i a_i \leq b$도 성립하고, $\sum_{i=1}^{m}c_i a_i \geq b$도 성립한다는 것을 의미하므로 $\left<a_1, \cdots, a_m, a_1, \cdots, a_m, b, b \right>$는 $KS$의 원소가 됩니다. 이의 역도 성립하므로, 위와 같이 정의한 함수 $f$가 조건을 만족한다는 사실을 증명할 수 있었습니다.
Clique Problem (클릭 문제)
위와 같은 그래프에서 B/C/F/H 이렇게 4개의 꼭짓점을 선택하면 이 4개의 꼭짓점 중 어느 2개를 선택하더라도 그 두 꼭짓점은 연결되어 있습니다. 이때, B, C, F, H를 이 그래프의 (크기가 4인) Clique이라고 합니다.
D, E, J나 B, C, H는 크기가 3인 Clique이 되며, 크기가 5인 Clique는 위 그래프에 존재하지 않습니다.
이를 이용해 Language $Clique$를 아래와 같이 정의하겠습니다.
$$Clique=\left\{\left<G,k \right>:k\in \mathbb{N}\wedge G\ has\ a\ clique\ with\ k\ vertices \right\}$$
예를 들어, 위의 그래프를 $G$라고 하면 $\left<G, 3 \right>, \left<G, 4 \right>$는 $Clique$의 원소이지만, $\left<G, 5 \right>$는 원소가 아닙니다.
이 $Clique$는 $\textbf{NP}$의 원소입니다.
3SAT Problem
잠시 클릭 문제는 접어두고, 다른 문제를 한번 보겠습니다.
$m$개의 Boolean (True 혹은 False의 값을 가지는 변수) $x_1, x_2, \cdots, x_m$ 가 있습니다. 그리고 이들의 부정, $\neg x_1, \neg x_2, \cdots, \neg x_m$도 존재합니다. 이들 중 임의로 3개를 골라서 OR 연산한 것을 $C_i$라고 하겠습니다. 예컨대 $x_1 \vee \neg x_1 \vee x_3$, $x_3 \vee x_5 \vee x_9$ 같은 것들이 있겠네요.
그리고 여러 개의 $C_i$들을 AND 연산한 것을 Boolean Formula라고 하고, 기호로는 $\varphi $라고 적습니다. 아래는 예시입니다.
$$\varphi = \left ( x_1 \vee \neg x_1 \vee \neg x_2 \right )\wedge \left ( x_3 \vee x_2 \vee x_4 \right )\wedge \left ( \neg x_1 \vee \neg x_3 \vee \neg x_4 \right )$$
만약 $x_i$들을 어떻게 어떻게 잘 잡아서, Boolean Formula를 참이 되도록 하는 $x_i$들이 존재하면 이 Boolean Formula는 Satisfiable이라고 합니다.
예를 들어, 위에 있는 Boolean Formula는 Satisfiable입니다. 왜냐? $x_1$을 0으로 잡고 $x_2$를 1로 잡으면 위 식은 아래와 같이 변합니다.
$$\varphi = \left ( 0 \vee 1 \vee 0 \right )\wedge \left ( x_3 \vee 1 \vee x_4 \right )\wedge \left ( 1 \vee \neg x_3 \vee \neg x_4 \right )$$
위 식에서 첫 번째 괄호는 참이고, 두 번째 괄호와 세 번째 괄호 역시 1이 포함되어 있으므로 항상 참이 됩니다. 따라서 $x_3$와 $x_4$가 어떤 값이든 위 Boolean Formula는 참이고, 따라서 Satisfiable입니다. 반면 $\left ( x_1 \vee x_1 \vee x_1 \right )\wedge \left ( \neg x_1 \vee \neg x_1 \vee \neg x_1 \right )$ 이런 Boolean Formula는 Not Satisfiable입니다. $x_1$이 어떤 값이 되든 위 식이 참이 될 수 없기 때문입니다.
이를 이용해 Language $3SAT$를 정의할 수 있습니다.
$$3SAT=\left\{\left<\varphi \right>:\varphi \ is\ satisfiable \right\}$$
이 $3SAT$ 역시 $\textbf{NP}$의 원소입니다.
클릭 문제와 3SAT
이렇게 클릭 문제와 3SAT 문제에 대해 연달아 알아보았는데요. 이 2개의 문제는 완전히 다른 Language처럼 보이지만, 사실 아래가 성립합니다.
$$3SAT \leq _P Clique$$
즉, 3SAT 문제를 클릭 문제로 변환할 수 있다는 것이죠. Boolean Formula $\varphi =C_1 \wedge C_2 \wedge \cdots \wedge C_k$에 대한 3SAT 문제는 아래와 같은 방법을 통해 $\left (G,k \right )$에 대한 클릭 문제로 변환할 수 있습니다.
- $G$의 꼭짓점은 $\left\{v_1^1, v_2^1, v_3^1, \cdots, v_1^k, v_2^k, v_3^k \right\}$ 입니다.
- 두 꼭짓점 $v_a^i$와 $v_b^j$에 대해, $i\neq j$ 이며 $v_a^i$가 $v_b^j$의 부정도 아니면 두 꼭짓점을 연결합니다.
예를 들면, 아래와 같습니다.
첫 번째 괄호에 해당하는 꼭짓점은 상단에, 두 번째 괄호에 해당하는 꼭짓점은 왼쪽, 세번째 괄호에 해당하는 꼭짓점은 오른쪽에 배치되어 있습니다. 첫번째 규칙에 의해 같은 괄호에서 나온 꼭짓점들은 서로 이어져있지 않습니다. 그리고 두번째 규칙에 의해 $x_1$은 $\neg x_1$과 이어져있지 않고, $\neg x_2$는 $x_2$와 이어져있지 않고, 이런 식입니다.
이런 식의 변환을 거치면 3SAT 문제를 클릭 문제로 변환할 수 있습니다. 그럼 왜 이렇게 되는 걸까요?
먼저 $\varphi =C_1 \wedge C_2 \wedge \cdots \wedge C_k$가 Satisfiable이라고 가정해 보겠습니다. 그러면 위 식을 참으로 만드는 $x_i$ 값들이 존재한다는 것이겠죠. 이때, 각 $C_i$를 $l_1^i \vee l_2^i \vee l_3^i$라고 하면 적어도 하나의 $l_a^i$는 참입니다.
따라서 각 $i$에 대해 $v_1^i, v_2^i, v_3^i$ 중 참에 대응되는 꼭짓점을 정확히 하나씩 선택해서 만든 꼭짓점의 집합을 정의할 수 있습니다. 이 집합을 $V'$이라고 하겠습니다. 그러면 이 $V'$은 $k$의 크기를 가지며, Clique입니다.
$V'$의 크기가 $k$라는 사실은 따로 증명할 필요가 없겠죠. 만약 $V'$이 Clique이 아니라면 서로 이어져있지 않은 두 꼭짓점 $v_a^i, v_b^j$가 존재해야 하는데, 이건 저희가 그래프를 구축할 때 배제한 케이스이므로 모순이 발생합니다. 따라서 $V'$은 Clique입니다.
마무리
이번 글에서는 $\textbf{NP}$에 해당하는 대표적인 문제 3가지. 가방 문제, 클릭 문제, 3SAT 문제에 대해 알아보았습니다.
감사합니다.
이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.