Satisfiability Problem

상위 문서: NP-Completeness

개요

SAT(Satisfiability Problem)는 컴퓨터 과학 이론에서 가장 유명한 NP-complete 문제이며, 전 세계의 알고리즘 전문가들이 빠른 알고리즘(다항시간)을 찾으려 했지만 실패했다. SAT를 빠르게 풀 수 있으면 P = NP가 되어버리며, NP 문제들이 전부 빠르게 풀려 암호 시스템 대부분이 붕괴한다.

Definition of SAT

SAT는 아래와 같은 문제 정의를 가진다:

입력: 변수들의 집합 $V$ 
    변수들로 이루어진 절(clause)들의 집합 $C$
질문: 변수들에 true/false 값을 적절히 넣어 모든 절(clause)이 동시에 참이 되도록 하는 방법이 존재하는가? 

아래는 SAT 문제에 대한 예시 인스턴스이다:

입력: $V=\{v_1,v_2\}$
    $C=\{\{v_1,\overline{v_2}\},\{\overline{v_1},v_2\}\}$

위와 같은 인스턴스에 대한 답은 모든 절을 참으로 만들 수 있다는 것이다. $v_1=v_2=true$로 놓으면 두 절이 모두 만족되기 때문이다. 반면, 아래와 같은 인스턴스는 만족 불가능하다:

입력: $V=\{v_1,v_2\}$
    $C=\{\{v_1,v_2\},\{v_1,\overline{v_2}\},\{\overline{v_1}\}\}$	

3-Satisfiability Problem

3-SAT(3-Satisfiability)은 SAT 문제의 특수한 버전으로, 각 절(clause)에 정확히 3개의 literal이 들어간 형식이다. 이는 SAT의 특수한 버전이기 때문에($3-SAT\subseteq SAT$), 만약 reduction에 따라 3-SAT이 NP-complete이면 SAT도 NP-complete이다.

SAT to 3-SAT Reduction

SAT의 절의 길이는 $k=1,2,3,4,..$으로 일반적인 길이를 가지기 때문에, 어떤 인스턴스의 각 절 $C_i$를 독립적으로 길이가 3인 절로 바꾸어 전체 식을 3-SAT 인스턴스로 변환하여 reduction을 수행할 수 있다.

먼저 $C_i=\{z_1\}$과 같이 $k=1$인 경우, 리터럴이 3개인 절로 만들기 위해서 새로운 변수 $v_1,v_2$ 2개를 만들어야 한다. 이 경우 아래와 같이 네 개의 절이 생성된다:

$\{v_1,v_2,z_1\}$
$\{v_1,\overline{v_2},z_1\}$
$\{\overline{v_1},v_2,z_1\}$
$\{\overline{v_1},\overline{v_2},z_1\}$

위 네 절이 동시에 만족되기 위해서는 무조건 $z_1=true$여야 하므로 원래의 의미가 보존된다.

그리고 $C_i=\{z_1,z_2\}$과 같이 $k=2$인 경우, 리터럴이 3개인 절로 만들기 위해서 새로운 변수 $v_1$을 만들어야 한다. 이 경우 아래와 같이 두 개의 절이 생성된다:

$\{v_1,z_1,z_2\}$
$\{\overline{v_1},z_1,z_2\}$

위 두 절이 모두 만족되기 위해서는 $z_1$ 또는 $z_2$ 중 하나가 true여야 하므로 원래 절의 의미가 유지된다.

마지막으로 $C_i=\{z_1,z_2,z_3,...,z_n\}$과 같이 $k=n>3$인 경우, 리터럴이 3개인 절로 만들기 위해서는 새로운 변수들 $v_1,v_2,\cdots ,v_{n-3}$를 만들고 아래와 같이 사슬형(chain) 절들을 만들어야 한다.

$\{z_1,z_2,v_1\}$
$\{\overline{v_1},z_3,v_2\}$
$\{\overline{v_2},z_4,v_3\}$
...
$\{\overline{v_{n-3}},z_{n-1},z_n\}$

위 절들은 각 절이 3개의 리터럴을 포함하도록 분해한 구조이다. 이를 통해서 원래의 절의 의미들을 보존할 수 있다. 또한 이를 통해서 $k$가 자연수일 때 모든 절들을 길이가 3인 절로 변환할 수 있다는 것이 증명되었다. 따라서 SAT $\le$ p 3-SAT이며, SAT는 NP-complete 이므로 3-SAT도 NP-complete이다.

이때, 절이 4개, 5개 … literal로 구성되어 있어도 조금 조정하면 동일한 방식으로 3-SAT으로 변환할 수 있기 때문에 4-SAT, 5-SAT, … 도 모두 NP-complete이다. 하지만 사실, 2-SAT 자체는 NP-complete이 아니며, 다항시간 내에 해결된다.

또한 어떤 문제에 대해 NP-complete 증명을 할 때 일반 SAT 대신 3-SAT를 기준 문제로 사용할 수 있다. 이때 3-SAT를 기준으로 사용하는 이유는 모든 절의 길이가 3으로 균일하여 구조가 더욱 규칙적이기 때문이다. 이때 reduction의 방향성은 아래와 같다:

SAT $\le$ 3-SAT $\le$ X

즉, SAT 문제를 3-SAT로 바꿀 수 있으므로, 3-SAT를 증명하고자 하는 X라는 새로운 문제로 reduction하여야 X가 NP-complete임을 증명할 수 있다. 예를 들면, Vertex Cover 혹은 Independent Set 문제는 3-SAT을 이용하여 NP-complete임을 증명할 수 있다.