[CM301] 13. NP-complete: SAT (Satisfiability problem)
![[CM301] 13. NP-complete: SAT (Satisfiability problem)](/CMajor/assets/img/thumbnails/cm301/13.png)
이번 절부터는 NP 문제의 가장 기초인 SAT 문제부터 시작하여 어떤 문제들이 NP-complete인지 알아보고, 그것들이 어떻게 NP-complete임을 보일 수 있는지 알아봅시다.
만족 가능성 문제(Satisfiability problem, SAT)
SAT는 어떤 논리식이 있을 때, 그 식의 결과가 참(True)이 되게 하는 입력값이 있는지를 묻는 문제입니다. 이전 절에서 예시로 들었던 자물쇠 문제와 비슷하죠? 여기에 입력값을 0 부터 9 대신 0 과 1로 바꾼 형태라고 생각하면 됩니다.
SAT에서 주어지는 논리식은 일반적으로 논리곱의 표준형Conjunctive Normal Form, CNF으로 나타내어집니다. CNF는 논리항들이 AND 연산으로 묶인 형태이며, 각 논리항들은 그 아래 항들이 OR 연산으로 묶여져 만들어집니다.
\[(x_1∨¬x_2)∧(x_2∨x_3)\]SAT는 NP문제의 가장 기초적인 형태로, 쿡-레빈 정리Cook-levin Theorem를 통해 NP-complete임을 보일 수 있습니다. 쿡-레빈 정리의 내용을 간단하게 요약해보겠습니다.
SAT: NP임을 보이기
SAT가 NP임을 보이기는 어렵지 않습니다. 자물쇠 문제에서 그랬던 것 처럼, 어떤 입력값을 넣었을 때 논리식의 결과가 참인지 확인하는 데에 시간이 오래 걸리지 않으니까요. 입력값을 넣어 논리식을 계산하는 데에는 항상 다항시간이 걸리므로, SAT는 NP라고 할 수 있습니다.
SAT: NP-hard임을 보이기
이 부분은 범위 밖의 개념이 등장하기 때문에 조금 어렵습니다! 설명을 자세히 하지는 않았으니, 그냥 넘어가도 무방한 부분입니다.
SAT가 NP-hard임을 보이기는 어렵습니다. NP-hard임을 보이기 위해서는 모든 NP 문제가 SAT로 환원될 수 있음을 보여야 합니다. 우선 임의의 NP 문제 $L$이 있을 때, 비결정론적 튜링 머신(Nondeterministic Turing Maching, NTM)라는 가상의 계산 기계 모델로 나타내야 합니다.
튜링 머신은 입력값과 상태값에 따라 행동이 변하는 가상의 계산 기계입니다. 행동은 크게 다른 입력값 받기, 상태값을 바꾸기, 현재 받은 입력값의 종류 바꾸기로 나뉩니다. 일반적으로 한 번의 입력에 한 번의 동작이 시행되지만, ‘비결정론적’ 튜링 머신은 한 번의 입력에 여러개의 동작이 동시에 시행된다는 차이가 있습니다. 일반적인 튜링 머신에 대해서는 ‘이산수학’ 포스트에서 자세히 다루었습니다.
NTM $M$은 다음과 같이 정의할 수 있습니다.
\[L \in NP \; \rightarrow \; M=(Q, \Sigma, s, \sqcup, F, \delta) \in L\]여기서 각각의 기호는
$Q$ : 상태값의 집합
$\Sigma$ : 입력값의 집합
$s$ : 초기 상태
$\sqcup$ : 빈 입력값에 대한 기호
$F$ : 종료 상태. 이 상태에 들어서야 NTM이 종료됩니다.
$\delta$ : 전이 함수. 입력값과 상태값에 따라 다음 동작을 결정합니다.
이렇게 NP 문제를 NTM으로 나타낼 수 있는 이유는, ‘다항 시간 안에 검토가 가능하다’라는 NP의 정의가 ‘비결정론적 튜링 머신(NTM)으로 다항시간에 풀 수 있는 문제’라는 정의로도 나타낼 수 있기 때문입니다.
NTM에는 몇 가지 규칙이 있습니다. 여러 개의 입력값을 동시에 받지 않고, 여러 개의 상태를 동시에 가지지 않으며, 현재의 입력값을 수정할 때는 다른 입력값을 받지 않는다, 이런 것들이요. 이 규칙들을 전부 논리항으로 표현합니다. 아래는 그 예시중 일부입니다.
| 규칙 | 규칙을 만족하는 조건 | 논리항 |
|---|---|---|
| 여러 개의 상태를 동시에 가지지 않는다 | k번째 연산일 때 상태값이 q0이면, k번째 연산일 때 상태값이 q1이 아님 | $Q_{k,q0} \rightarrow \neg Q_{k,q1}$ |
| 여러 개의 입력값을 동시에 받지 않는다 | k번째 연산일 때 테이프 i번째 값이 j0이면, k번째 연산일 때 테이프 i번째 값이 j1이 아님 | $T_{i,j0,k} \rightarrow \neg T_{i,j1,k}$ |
| 현재의 입력값을 수정할 때는 다른 입력값을 받지 않는다 | k번째 연산일 때 테이프 i번째 값이 j0이었다가 k+1번째에 j1로 바뀌었다면, 제어장치는 k번째에 테이프 i번째를 가리키고 있음 | $T_{i,j0,k} \land T_{i,j1,k+1} \rightarrow H_{i,k}$ |
이것들을 전부 논리곱으로 합해 CNF로 나타낸다면, NTM을 정의하는 논리식 $B$를 만들어낼 수 있습니다. 이제 이 논리식이 참이 되는 입력값을 찾는 문제는 SAT가 됩니다.
\[B = (Q_{k,q0} \rightarrow \neg Q_{k,q1}) ∧ (T_{i,j0,k} \rightarrow \neg T_{i,j1,k}) ∧ (T_{i,j0,k} \land T_{i,j1,k+1} \rightarrow H_{i,k}) ∧ ...\]
이제 $M$이 어떤 입력값을 받았을 때, 그에 대응되는 논리항을 $B$에 넣으면 참이 될 것입니다. 반대로, $B$이 참이 되는 논리항들이 있을 때, $M$은 이에 대응되는 입력값을 받을 수 있습니다. 그러므로 $M$이 $B$와 완벽하게 대응된다고 할 수 있겠죠.
\[M \in L \; \Leftrightarrow \; B = f(M) \in SAT\]결정적으로 $M$을 $B$로 바꾸는 함수 $f$는 다항시간이 걸립니다. 따라서 우리는 주어진 NP 문제인 $M$을 SAT 문제인 $B$로 환원시킬 수 있게 됩니다.
\[L \leq_p SAT\]임의의 NP 문제에 대해서 SAT로 환원시킬 수 있으니, SAT는 NP-hard라고 할 수 있습니다.
그러므로 SAT는 NP-complete입니다. SAT를 풀어서 설명하면, ‘주어진 논리 조건들을 모두 만족하는 해가 존재하는가?’라고 말할 수 있습니다. 그리고 모든 NP 문제들을 이 질문으로 바꾸어 말할 수 있게 되는 것이죠. 앞으로 다룰 모든 NP-complete 문제들도 SAT를 환원하여 나타낼 수 있습니다.
3-SAT
3-SAT 문제는 SAT 문제에서 주어지는 CNF식에 조건이 추가된 조금 특별한 경우입니다. CNF에서 AND 연산으로 묶이는 각 논리항들은 반드시 세 개의 항이 OR 연산으로 묶인 형태를 가져야 합니다. 이런 형태를 3-CNF라고 합니다.
\[(x_1 ∨ x_2 ∨ ¬x_3)∧(x_1 ∨ x_2 ∨ ¬x_4)∧\dots\]3-SAT도 NP-complete임을 보일 수 있을까요?
3-SAT: NP임을 보이기
SAT와 마찬가지로 입력값을 넣어 논리식을 계산하는 데에는 항상 다항시간이 걸립니다. 따라서 3-SAT는 NP라고 할 수 있습니다.
3-SAT: NP-hard임을 보이기
NP-hard임을 보이는 또다른 방법은 NP-hard임을 알고 있는 다른 문제가 이 문제로 환원될 수 있음을 보이는 것이었습니다. 일단 3-SAT는 SAT의 특별한 경우이니, 당연히 SAT로 환원할 수 있겠죠.
\[\text{3-SAT} \leq_p \text{SAT}\]하지만 증명을 위해 우리가 알아야 하는 것은 SAT가 3-SAT로 환원될 수 있는가입니다.
\[\text{SAT} \leq_p \text{3-SAT}\]즉, 모든 CNF를 3-CNF로 바꿀 수 있는가?라는 질문을 해결해야합니다. 놀랍게도 여기에 해답이 존재하는데, 우리는 몇 가지 단계를 따라가야 합니다.
쉬운 이해를 위해 간단한 예시를 하나 들어봅시다.
\[(y_1 = x_1 ∨ x_2)∧(y_2 = ¬x_2 ∨ x_3)∧(y_3 = ¬x_4)∧(z = y_1 ∧ y_2 ∧ y_3)∧z\]
보다시피, 임의의 SAT는 3-SAT와 다른 점이 많습니다. 논리항이 OR로만 묶여 있지도 않고, 세 개의 항으로만 이루어져 있지도 않거든요. 우선, 한 번에 세 개 이상의 항들을 묶는 연산($z = y_1 ∧ y_2 ∧ y_3$)을 두 개 이하의 항들로 나누어주겠습니다.
\[(y_1 = x_1 ∨ x_2)∧(y_2 = ¬x_2 ∨ x_3)∧(y_3 = ¬x_4)∧(z_1 = y_1 ∧ y_2)∧(z_2 = z_1 ∧ y_3)∧z_2\] 그리고 3-SAT에는 없는 = 연산을 다른 연산으로 치환합니다.
$a = b ∧ c \rightarrow (a ∨ ¬b ∨ ¬c)∧(¬a ∨ b)∧(¬a ∨ c)$
$a = b ∨ c \rightarrow (¬a ∨ b ∨ c)∧(a ∨ ¬b)∧(a ∨ ¬c)$
$a = ¬b \rightarrow (a ∨ b) ∧ (¬a ∨ ¬b)$
마지막으로 두 개 이하의 항으로 이루어신 논리항을 세 개의 항이 되도록 바꾸어주면 됩니다.
$a \rightarrow (a ∨ x ∨ y) ∧ (a ∨ ¬x ∨ y) ∧ (a ∨ x ∨ ¬y) ∧ (a ∨ ¬x ∨ ¬y)$
$a b \rightarrow (a ∨ b ∨ x) ∧ (a ∨ b ∨ ¬x)$
이제 최종적으로 완성된 3-CNF 식을 보면…
\[\begin{aligned} (¬ y_1 ∨ x_1 ∨ x_2) ∧ (y_1 ∨ ¬ x_1 ∨ u_1) ∧ (y_1 ∨ ¬ x_1 ∨ ¬ u_1) ∧ (y_1 ∨ ¬ x_2 ∨ u_2) ∧ (y_1 ∨ ¬ x_2 ∨ ¬ u_2) \\ ∧ (¬ y_2 ∨ ¬ x_2 ∨ x_3) ∧ (y_2 ∨ x_2 ∨ u_3) ∧ (y_2 ∨ x_2 ∨ ¬ u_3) ∧ (y_2 ∨ ¬ x_3 ∨ u_4) ∧ (y_2 ∨ ¬ x_3 ∨ ¬ u_4) \\ ∧ (¬ y_3 ∨ ¬ x_4 ∨ u_5) ∧ (¬ y_3 ∨ ¬ x_4 ∨ ¬ u_5) ∧ (y_3 ∨ x_4 ∨ u_6) ∧ (y_3 ∨ x_4 ∨ ¬ u_6) \\ ∧ (z_1 ∨ ¬ y_1 ∨ ¬ y_2) ∧ (¬ z_1 ∨ y_1 ∨ u_7) ∧ (¬ z_1 ∨ y_1 ∨ ¬ u_7) ∧ (¬ z_1 ∨ y_2 ∨ u_8) ∧ (¬ z_1 ∨ y_2 ∨ ¬ u_8) \\ ∧ (z_2 ∨ ¬ z_1 ∨ ¬ y_3) ∧ (¬ z_2 ∨ z_1 ∨ u_9) ∧ (¬ z_2 ∨ z_1 ∨ ¬ u_9) ∧ (¬ z_2 ∨ y_3 ∨ u_{10}) ∧ (¬ z_2 ∨ y_3 ∨ ¬ u_{10}) \\ ∧ (z_2 ∨ v_1 ∨ v_2) ∧ (z_2 ∨ ¬ v_1 ∨ v_2) ∧ (z_2 ∨ v_1 ∨ ¬ v_2) ∧ (z_2 ∨ ¬ v_1 ∨ ¬ v_2) \end{aligned}\]
…아무튼 문제 없이 CNF를 3-CNF로 바꿀 수 있습니다!
3-CNF로 변환하는 과정은 각 논리항 마다 상수 시간의 연산이 필요하므로, 전체는 다항시간이 걸리게 됩니다. 따라서 SAT는 3-SAT로 환원될 수 있고, SAT가 NP-hard임을 알고 있으니 3-SAT 또한 NP-hard임을 보일 수 있습니다.
\[\text{SAT} \leq_p \text{3-SAT}\]3-SAT는 NP 이면서 NP-hard이니, NP-complete입니다. 앞으로 다른 문제들도 이전에 NP-hard임을 보였던 문제들을 환원함으로서 NP-complete임을 증명하게 될 것입니다.