3-SAT <-> Clique

3-SAT -> Clique 환원

F=(x1​∨¬x2​∨x3​)∧(¬x1​∨x2​∨¬x3​)

환원 단계 요약 아이디어:
각 절에서 하나씩 리터럴을 선택하되,
모순이 없는 조합끼리만 간선을 연결
→ 그런 간선들로 클릭(K) 크기의 완전 그래프가 존재하면 만족 가능

Step 1. 절마다 리터럴 → 노드 만들기

노드 이름 내용절 번호

v₁	x1​	C₁
v₂	¬x2	C₁
v₃	x3	C₁
v₄	¬x1	C₂
v₅	x2	C₂
v₆	¬x3	C₂

총 6개의 노드를 만들었다.
각 노드는 어느 절에서 어떤 리터럴인지 기억하고 있음.

Step 2. 간선 연결 규칙
다음 조건을 만족할 때만 간선을 연결한다.
1. 두 노드가 다른 절에서 나왔을 것
2. 두 리터럴이 모순되지 않을 것 (예: \(x_1​ \text{ vs } \neg x_1\) <- NO

절 C₁ 노드 ↔ 절 C₂ 노드 조합 중 모순 없는 것만 연결

조합 간선 가능? 이유

v₁ (x₁) — v₄ (¬x₁)	모순
v₁ — v₅ (x₂)	OK
v₁ — v₆ (¬x₃)	OK
v₂ (¬x₂) — v₄	OK
v₂ — v₅	모순
v₂ — v₆	OK
v₃ (x₃) — v₄	OK
v₃ — v₅	OK
v₃ — v₆	모순

노드:

절 C₁: v₁(x₁), v₂(¬x₂), v₃(x₃)

절 C₂: v₄(¬x₁), v₅(x₂), v₆(¬x₃)

간선 연결 (가능한 조합만):

복사편집

v₁ — v₅
v₁ — v₆
v₂ — v₄
v₂ — v₆
v₃ — v₄
v₃ — v₅

• 이제 CLIQUE of size 2를 찾는 문제가 됐다.
  (왜냐면 절이 2개니까, 각 절에서 하나씩 뽑아 연결된 두 노드가 필요)
• 가능한 해 예시:
  • v₃ (x₃), v₅ (x₂): 둘은 서로 연결되어 있고, 각각 다른 절에서 나옴 → OK
  • 해석: x2=T, x3=T 하면 원래 식 F도 만족됨

Clique -> 3-SAT 환원

목표:

어떤 그래프 G=(V,E)G = (V, E)G=(V,E)와 자연수 k에 대해,
"크기 k의 클리크가 존재하는가?" 를
→ 3SAT 식이 만족 가능한가? 문제로 바꾸기

예제 아주 작은 그래프 G:

정점 \(\{1, 2, 3, 4\}\)

간선 E = \(\{(1,2), (2,3), (1,3), (3,4)\}\)

(시각적으로는 1-2-3이 삼각형 형태, 3-4 연결만 더 있음)

목표: k = 3 크기의 클리크가 존재하는가?

→ 실제로 (1,2,3)은 서로 연결되어 있으므로 클리크 존재함

CLIQUE → 3SAT 환원 아이디어

k개의 정점을 선택해서 모두 서로 연결되게 만들기
→ 이걸 논리 변수 + 조건으로 표현할 수 있음

변수 설정:

• \(x_{i,j}:\)
  "위치 j에 정점 i를 배정했다"는 뜻
  • i∈V (정점 번호)
  • j= 1,...,kj = 1, ..., k (클리크 내 위치)

예: \(x_{3,2}\)=True → "두 번째 위치에 정점 3을 배치"

구성해야 할 제약 (절들)

제약 1: 각 위치에 하나의 정점만 배치

(중복 없음)

• 예: 위치 1에 1 또는 2 또는 3 또는 4 중 하나만 와야 함
  → (x1,1∨x2,1∨x3,1∨x4,1) \( (x_{1,1} \lor x_{2,1} \lor x_{3,1} \lor x_{4,1})\)(x1,1​∨x2,1​∨x3,1​∨x4,1​)
• 그 외 위치들도 마찬가지

제약 2: 한 정점이 두 위치에 동시에 나오면 안 됨

(같은 정점이 중복되지 않도록)

• \( \neg(x_{1,1} \land x_{1,2}) → (\neg x_{1,1} \lor \neg x_{1,2})\)

모든 i, 모든 \( j_1 \ne j_2 \)에 대해 생성

제약 3: 선택된 두 정점은 연결되어 있어야 함

• 즉, **정점 i, j**가 간선으로 연결되지 않았으면
  → 둘 다 클리크에 들어올 수 없음
• 예: 정점 1과 4는 간선 없음 →

\(\neg x_{1,1} \lor \neg x_{4,2} \quad (\text{위치 1에 1, 위치 2에 4는 불가})\)

이런 식으로 비연결 정점 쌍에 대해 금지 조건을 생성

 

요약 흐름

CLIQUE 문제 구성	대응되는 3SAT 구성
정점 선택	변수 (x_{i,j})
선택은 하나만	각 위치에 1개 리터럴
중복 제거	¬xi,j1​​∨¬xi,j2​​
연결 조건 보장	비연결 노드에 대해 ¬xi,j​∨¬xk,j′