[계산이론] #14. NP-Complete (2)
지난 글에서 NP-Complete가 무엇인지, 그리고 어떤 언어가 NP-Complete임을 어떻게 증명할 수 있는지에 대해 알아보았었습니다. 이 글에서는 NP-Complete에 속하는 언어의 예시에 대해 좀 더 알아보겠습니다.
SAT Problem
지난 글에서 간단하게 다루었던 문제이지만 다시 설명하고 넘어가겠습니다.
이 문제에는 $m$개의 Boolean, $x_1,x_2, \cdots, x_m$이 존재합니다. 이들은 0 혹은 1의 값을 가지며 0은 False를, 1은 True를 의미합니다. 그리고 $x_j$의 Negation은 $\neg x_j=1-x_j$로 정의됩니다. 이 둘을 합쳐서 Literal, $l$ 이라고 부릅니다. 그리고 몇 개의 Literal을 논리합 (OR) 연산한 것을 Clause라고 합니다. 예를 들어, $x_1 \vee \neg x_3 \vee x_4$는 3개의 Literal로 이루어진 Clause입니다.
그리고 $k$개의 Clause를 논리곱 (AND) 연산한 것을 Boolean Formula, $\varphi$ 라고 합니다.
$$\varphi =C_1 \wedge C_2 \wedge \cdots \wedge C_k$$
어떤 Boolean Formula를 참으로 만드는 $x_1,x_2, \cdots, x_m$이 존재하면 이 Boolean Formula를 Satisfiable이라고 부르며, 참으로 만드는 $x_1,x_2, \cdots, x_m$이 존재하지 않으면 Not Satisfiable이라고 합니다.
그리고 Satisfiable한 모든 Boolean Formula의 집합을 $SAT$라고 정의하겠습니다. 지난번에 보았던 $3SAT$의 연장선이죠. 저희는 이 $SAT$가 $\textbf{NP-Complete}$임을 증명해 보겠습니다.
지난 글에서 언급했듯 어떤 언어가 $\textbf{NP-Complete}$임을 증명하는 방법은 바로 $Domino\leq_P SAT$임을 보이는 것입니다. 지난 글에서 $Domino$는 $\textbf{NP-Complete}$임이 증명되었기 때문이죠.
$Domino\leq_P SAT$임을 보이려면, 도미노 게임을 $SAT$ 문제로 변환하는 함수 $f \in \textbf{FP}$를 제시해야 합니다. 방법이 복잡하기 때문에 간단히 설명하겠습니다.
먼저, 도미노 게임의 $i$번째 행, $j$번째 열에 $l$번째 타일이 있다는 의미로 저희는 Boolean $x_{ijl}$의 값이 1이라는 사실을 이용할 겁니다. 이때 아래와 같이 Clause들을 정의합니다.
만약 $C_{ij}^1$가 1이라면, $\left ( i,j \right )$에 적어도 하나의 타일이 있음을 의미합니다.
만약 $C_{ijll'}^2$가 1이라면, $\left ( i,j \right )$에 최대 1개의 타일이 있음을 의미합니다.
$C_{ijll'}^3$은 $\left ( i,j \right )$에 있는 타일과 $\left ( i,j+1 \right )$에 있는 타일이 서로 맞는지, 맞지 않는지를 의미합니다.
$C_{jl}^4$는 $j$번째 열의 첫 타일이 바로 위에 있는 Frame과 맞는지, 맞지 않는지를 의미합니다. 비슷한 방법으로 아래쪽, 왼쪽, 오른쪽 Frame에 대한 Clause도 만들 수 있습니다.
이렇게 만들어진 4개 Caluse를 곱연산한 것을 $\varphi $라고 두면, 도미노 게임을 $SAT$로 변환하는 과정이 끝납니다.
3SAT Problem
$3SAT$ 문제는 $SAT$ 문제 중 Literal이 3개인 Clause로만 구성된 것들을 말합니다. 직관적으로, $3SAT$가 특별히 $SAT$에 비해 어려울 이유가 없기 때문에, $3SAT$문제 역시 NP-Complete임을 알 수 있습니다.
$$C=x_1 \vee x_2 \vee x_3 \vee x_4$$
위와 같이 4개의 Literal로 구성된 Clause가 있습니다. 이때 새로운 변수 $z$를 만들어서, 이 Clause를 다음과 같이 변형시킬 수 있습니다.
$$C'=\left ( x_1 \vee x_2 \vee z \right ) \wedge \left ( \neg z \vee x_3 \vee x_4 \right )$$
만약 $C$가 1이라면 아래 2가지 경우 중 하나가 항상 성립합니다.
- $ x_1 \vee x_2 $가 1일 경우 $z$를 0으로 잡으면, $C'$도 1입니다.
- $ x_3 \vee x_4 $가 1일 경우 $z$를 1로 잡으면, $C'$도 1입니다.
따라서 $C$가 1이면 $C'$을 1로 만드는 $z$가 존재합니다. 반대로, $C'$이 1이 되도록 하는 $z$가 존재한다면, 아래 2가지 경우 중 하나가 항상 성립합니다.
- $z$가 0일 경우 $ x_1 \vee x_2 $가 1이어야 합니다. 따라서, $C$도 1입니다.
- $z$가 1일 경우 $ x_3 \vee x_4 $가 1이여야 합니다. 따라서, $C$도 1입니다.
따라서 $C'$이 1이 되도록 하는 $z$가 존재한다면 $C$가 1입니다. 따라서 이런 방법으로 4개의 Literal을 가진 Clause를 3개의 Literal을 가진 2개의 Clause로 분해할 수 있었습니다.
똑같은 방식으로, 5개의 Literal을 가진 Clause $C=x_1 \vee x_2 \vee x_3 \vee x_4 \vee x_5 $는 아래와 같이 변형 가능합니다.
$$C'=\left ( x_1 \vee x_2 \vee z_1 \right ) \wedge \left ( \neg z_1 \vee x_3 \vee z_2 \right ) \wedge \left ( \neg z_2 \vee x_4 \vee x_5 \right )$$
이렇게 3개 이상의 Literal로 이루어진 $SAT$ 문제들을 전부 3개의 Literal로 이루어진 $3SAT$ 문제로 변형 가능하므로, $3SAT$ 문제도 NP-Complete임이 증명되었습니다.
Another NP-Complete Problems
아래의 문제들도 전부 NP-Complete입니다. 증명은 생략합니다.
- Hamilton Cycle (HC) : 주어진 그래프의 모든 꼭짓점을 지나는 Cycle이 존재하는지 판별하는 문제
- Traveling Salesman Problem (TSP) : $m$개의 도시와 도시 간의 거리가 주어져 있을 때 길이가 $k$를 넘지 않는 Cycle이 존재하는지 판별하는 문제
- Clique : 주어진 그래프에 $k$개의 꼭짓점으로 구성된 Clique(모든 꼭짓점끼리 연결되어 있는 그래프)이 존재하는지 판별하는 문제
- Sum of Subste (SOS) : 주어진 $m$개의 $a_i$ 중 임의로 몇 개를 선택하여 합이 $b$가 되도록 할 수 있는지 판별하는 문제
- Bin Packing : 각각의 부피가 $a_i$인 $m$개의 물체와, 부피 $l$을 가진 Bin $k$개가 있을 때 Bin에 모든 물체를 넣을 수 있는지 없는지를 판별하는 문제
감사합니다.
이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.