투셋(2-sat)

2-SAT 문제를 해결하기 앞서 먼저 용어 정리부터 필요하다.

 

CNF (Conjunctive Normal Form)

• $(x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3) \wedge (x_2 \vee \neg x_3 \vee x_4)$...
• $\vee$로 이루어진 절이 최대 k개이면 k-CNF
• 모든 k-CNF 는 3-CNF로 변형 가능

 

k-SAT(k-satisfiability problem)

k-SAT 문제는 $\vee$(OR)로 이루어진 k개의 논리 변수가 $\wedge$(AND) 로 묶인 논리식을 만족(True)시키는 조합을 찾는 문제이다.

• k-SAT은 3-SAT으로 변형 가능하기 때문에 3-SAT과 2-SAT만 의미가 있음
• 3-SAT은 NP-complete (쿡-레빈 정리)
• 2-SAT은 다항시간에 가능(P)

위 정리와 같이 3-SAT은 NP-complete지만, 2-SAT은 다항 시간 내에 풀 수 있다.

그저 모든 변수(N개)에 대해 True, False를 전부 대입해 보면 충족가능한지 확인할 수 있겠지만 $2^N$ 이 소요되니 더 아름답게 다항 시간에 푸는 방법을 알아보자.

 

2-SAT

아래 논리식을 만족시키는 변수를 찾아보자.
$$(\neg x_1 \vee \neg x_2) \wedge (x_2 \vee \neg x_3) \wedge (x_3 \vee x_1)
\wedge (\neg x_2 \vee \neg x_3)$$

첫번째 항 $(\neg x_1 \vee \neg x_2)$ 을 먼저 보자. 이를 명제로 표시해보면 다음과 같다.

1. $x_1 \Rightarrow \neg x_2$
2. $x_2 \Rightarrow \neg x_1$

둘 중 하나 이상은 참이어야 한다는 식을 명제로 썼다. 나머지 모든 항에 대해서도 명제로 풀어쓰자.

1. $x_1 \Rightarrow x_3$
2. $\neg x_3 \Rightarrow \neg x_1$
3. $\neg x_1 \Rightarrow x_2$
4. $\neg x_2 \Rightarrow x_1$
5. $\neg x_2 \Rightarrow \neg x_3$
6. $x_3 \Rightarrow x_2$
7. $x_2 \Rightarrow \neg x_3$
8. $x_3 \Rightarrow \neg x_2$

이제 $x_i$와 $\neg x_i$를 node로, $\Rightarrow$를 edge로 변환해서 그래프를 그려보자.

논리식을 그래프로 바꿨다

 

 

그래프의 소스가 명제인 만큼 어느 하나의 노드가 true라면 화살표를 타고 간 다음 노드도 true가 되어야만 한다. 만약 다음 노드가 false라면 true $\Rightarrow$ false 가 되어버리기 때문이다.

결국 화살표로 연결된 하나의 큰 component는 같은 공동운명체를 타고난 셈인데, SCC를 이용해서 같은 공동체를 묶을 수 있다.

SCC(Strongly Connected Componet)

• 두 정점 u, v에 대해서 서로 갈 수 있으면 두 정점은 같은 SCC
• SCC에 대해서도 그래프로 구현하면 DAG(Directed Acyclic Graph)

 

SCC 

 

위 정의대로 SCC를 구하면 이렇게 $x_{1}, \neg x_{2}, x_{3}$과 $\neg x_{1}, x_{2}, \neg x_{3}$ 로 나눌 수 있다. 그리고 더 나아가 각 SCC 들 사이의 관계도 구할 수 있다.

scc 사이의 관계

 

 

SCC를 구하는 방법은 Kosaraju과 Tarjan 이 있다.
Kosaraju는 $u -> v, v -> u$ 처럼 서로 갈 수 있으면 같은 SCC라는 특징을 이용해서 모든 간선을 거꾸로 변형한 그래프를 이용해서 구하고, Tarjan은 그래프 탐색의 특징과 stack을 이용해서 구한다. 특히 Tarjan의 경우 결괏값으로 SCC의 위상 정렬까지 얻을 수 있어서 번거로움을 줄일 수 있다.

 

2-SAT 문제풀이에 집중을 하기 위해 SCC는 간략히 넘어가고, 이후 변숫값을 구하는 과정으로 넘어간다.

SCC까지 구한 그래프에서 각 값을 구하는 방법으로 모든 경우를 나열해서 풀어보면 다음과 같다.

 

• $x_i$와 $\neg x_i$가 같은 SCC에 존재하는 경우
  • 모순!
• $x_i$와 $\neg x_i$가 다른 SCC에 존재하는 경우
  • SCC가 부모-자식 관계인 경우
    • 먼저 나온 변수가 true일 경우
      • 그래프 타고 가다 보면 뒤에 나온 $\neg$ 변수도 true 여야 하기 때문에 모순!
    • 먼저 나온 변수가 false일 경우
      • 뒤에 나온 변수를 true로 설정 $\cdots$ (1)
  • SCC가 관계없는 경우
    • 아무 값이나 상관없음 $\cdots$ (2)

따라서 논리식을 모순 없이 만족시키는 (1), (2) 경우로만 식을 풀이하면 각 변수의 값(true | false)도 찾을 수 있다.

그래프 탐색 한번 $O(V+E)$ 에 SCC를 구한 후, 논리 값을 찾는 데는 단순히 모든 노드를 확인하는 비용밖에 들지 않기 때문에 2-SAT의 총 시간 복잡도는 $O(V+E)$가 되겠다.

 

정리

1. 주어진 2-CNF를 그래프로 변형
2. Tarjan algorithm으로 위상 정렬된 SCC를 구한 후
3. 앞서 살펴본 방법대로 한 번의 스캔으로 값을 구함