12.1.1 2-SAT

함축

함축

$$P\to Q\equiv \neg P\vee Q$$

즉, “$P$이면 $Q$이다”는 “$P$가 아니거나 $Q$이다”와 같다.

• 숙제를 하면, 과자를 받는다 $\equiv$ 숙제를 안했거나, 과자를 받았다.
  • T, T → T
  • T, F → F (숙제를 했는데, 과자를 안 준 경우만 거짓)
  • F, T → T
  • F, F → T

Link to original

2-SAT 문제

• 연습 문제
  • 티비 쇼 게임 - JUNGOL
    • JOJ Online Judge
  • 아이돌 - JUNGOL
    • JOJ Online Judge
• 참고
  • 2-SAT (알고리즘)
  • 참고자료 - TV Show Game

2SAT 문제에서는 다음과 같은 논리식을 다룬다.

$$(a_1\vee b_1)\wedge (a_2\vee b_2)\wedge \cdots \wedge (a_m\vee b_m)$$

여기에서 $a_i$와 $b_i$는 논리 변수 $(x_1,x_2,\dots ,x_n)$, 또는 논리 변수의 부정 $(\neg x_1,\neg x_2,\dots ,\neg x_n)$이다. $\wedge$와 $\vee$는 논리곱(and) 및 논리합(or) 연산을 의미하는 기호이다. 각 변수에 값을 할당하여 식을 참으로 만드는 조합을 찾거나, 그러한 조합이 없음을 찾는 것이 목표이다.

예를 들어 다음 식을 살펴보자.

$$L_1=(x_2\vee \neg x_1)\wedge (\neg x_1\vee \neg x_2)\wedge (x_1\vee x_3)\wedge (\neg x_2\vee \neg x_3)\wedge (x_1\vee x_4)$$

이 식은 값이 다음과 같을 경우에 참이다.

$$\{\begin{array}{l}{x}_1=\mathrm{false}\\ x_2=\mathrm{false}\\ x_3=\mathrm{true}\\ x_4=\mathrm{true}\end{array}$$

하지만 다음 식은 값을 어떻게 할당하든 항상 거짓이다.

$$L_2=(x_1\vee x_2)\wedge (x_1\vee \neg x_2)\wedge (\neg x_1\vee x_3)\wedge (\neg x_1\vee x_3)\wedge (\neg x_1\vee \neg x_3)$$

그 이유는 $x_1$의 값을 모순 없이 정할 수 없기 때문이다. $x_1$이 거짓이라면 $x_2$와 $\neg x_2$가 모두 참이어야 해서 불가능하고, $x_1$이 참이라면 $x_3$와 $\neg x_3$가 모두 참이어야 해서 역시 불가능하다.

2SAT 문제에서 제시되는 식을 함의 그래프(implication graph)로 나타낼 수 있다. 이때 노드는 변수 $x_i$ 및 부정형 $\neg x_i$에 대응되며, 간선은 변수 간의 관계를 표현한다. 각각의 항 $(a_i\vee b_i)$에 대해 $\neg a_i\to b_i$와 $\neg b_i\to a_i$의 두 간선을 만든다. 이는 $a_i$가 참이 아닐 경우 $b_i$가 참이어야 함을 의미하며, 반대의 경우도 마찬가지이다. 예를 들어 그림 6에 $L_1$의 함의 그래프가 나와 있으며, 그림 7에는 $L_2$의 함의 그래프가 나와 있다.

• 그림 6. $L_1$의 함의 그래프

  • 

• 그림 7. $L_2$의 함의 그래프

  • 

수식이 참이 되도록 모든 변수에 값을 할당하는 것이 가능한지 여부는 함의 그래프의 구조에 따라 결정된다. 가능한 경우는 $x_i$ 노드와 $\neg x_i$ 노드가 같은 강결합 컴포넌트에 속하는 일이 없는 경우와 동치이다. 같은 강결합 컴포넌트에 속한 노드가 있으면 $x_i$ 노드에서 $\neg x_i$ 노드로 가는 경로, 그리고 $\neg x_i$ 노드에서 $x_i$ 노드로 가는 경로가 모두 있다는 의미이다. 따라서 $x_i$와 $\neg x_i$가 모두 참이어야 하지만 이는 불가능하다.

예를 들어 $L_1$의 함의 그래프에서는 $x_i$와 $\neg x_i$가 같은 강결합 컴포넌트에 속하는 경우가 없으므로 해가 존재한다. $L_2$의 함의 그래프에서는 모든 노드가 같은 강결합 컴포넌트에 속하므로 해가 존재하지 않는다.

해가 존재하는 경우, 변수의 값은 컴포넌트 그래프의 모든 노드를 위상 정렬 역순으로 방문하면서 찾을 수 있다. 단계마다 처리하지 않은 컴포넌트로 향하는 간선이 없는 컴포넌트를 처리한다. 컴포넌트의 변수에 값이 할당되지 않았다면, 그 컴포넌트에 속한 변수들에 따라 그 값을 결정하고, 이미 값이 할당된 변수는 그 값을 유지한다. 이 과정을 모든 변수에 값이 할당될 때까지 진행한다.

그림 8에 $L_1$의 컴포넌트 그래프가 나와 있다. 각 컴포넌트는 $A=\{\neg x_4\}$, $B=\{x_1,x_2,\neg x_3\}$, $C=\{\neg x_1,\neg x_2,x_3\}$, $D=\{x_4\}$이다. 해를 찾기 위해 먼저 컴포넌트 $D$를 처리하며, $x_4$의 값은 참이 된다. 다음으로 컴포넌트 $C$를 처리하고, $x_1$과 $x_2$의 값은 거짓, $x_3$의 값은 참이 된다. 모든 변수에 값이 할당되었으므로 컴포넌트 $A$와 $B$를 처리할 때는 변수의 값이 바뀌지 않는다.

• 그림 8. $L_1$의 컴포넌트 그래프
  • 

이 방법이 성립하는 이유는 함의 그래프가 특별한 구조로 되어 있기 때문이다. $x_i$ 노드에서 $x_j$ 노드로 가는 경로, 그리고 $x_j$ 노드에서 $\neg x_i$ 노드로 가는 경로가 모두 있다면 $x_i$ 노드가 참이 될 수 없다. 그 이유는 $\neg x_j$ 노드에서 $\neg x_i$ 노드로 가는 경로도 있어서 $x_i$와 $x_j$가 모두 거짓이 되기 때문이다.

더 어려운 문제는 3SAT 문제인데, 이는 논리식의 각 항이 $(a_i\vee b_i\vee c_i)$의 형태로 되어 있는 경우이다. 이 문제는 NP-하드로, 효율적인 알고리즘이 알려지지 않았다.

2-SAT 구현 절차

•   절 (a ∨ b)
    	↓
    간선 ¬a -> b, ¬b -> a 생성
    	↓
    함의 그래프 완성
    	↓
    SCC 분해
    	↓
    x와 ¬x가 같은 SCC에 있는지 확인
    	↓
    있으면 불가능
    없으면 가능
    	↓
    컴포넌트 DAG의 위상 순서를 이용해 값 배정