3-SAT -> SUBSET SUM

좋아, 이건 진짜 명작 환원이야.

**3SAT → SUBSET SUM**은

서로 완전히 다른 문제 세계인 **불 논리식**과 **정수 덧셈** 사이를

수학적으로 **완벽하게 대응**시키는 예술적인 구조지.

 

---

 

## 🎯 목적

 

> 어떤 3SAT 식이 주어졌을 때,

> 이를 만족시키는 변수 할당이 존재하는지

> → **SUBSET SUM** 문제로 바꿔서 판단

 

즉,

 

\[(x_1 \lor \neg x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor \neg x_3)\]

 

이런 논리식을

→ 정수들의 집합과 목표합 $T$으로 변환해서

→ "부분집합의 합이 $T$가 되도록 고를 수 있는가?"로 바꾼다.

 

---

 

##  SUBSET SUM 문제란?

 

* 입력: 정수 집합 $S = \{s_1, s_2, ..., s_n\}$, 목표합 $T$

* 문제: $S$에서 일부 원소를 골라 합이 정확히 $T$가 되는가?

 

---

 

## 3SAT → SUBSET SUM 환원의 핵심 아이디어

 

### 핵심 철학:

 

> **변수를 선택한다** = **어떤 수를 고른다**

> **절을 만족시킨다** = **특정 자리수의 합이 조건을 만족한다**

 

→ **자리수 기반의 인코딩**이 포인트

 

---

 

## 환원 설계 개요

 

### 입력:

 

3SAT 식 with

 

* $n$개의 변수

* $m$개의 절 (각 절에 3개의 리터럴)

 

### 출력:

 

SUBSET SUM 문제 with

 

* $2n$개의 숫자 (각 변수의 참/거짓 선택지)

* 목표 합 $T$:

 

  * 변수 자리 합이 $n$

  * 각 절 자리 합이 ≥1 → 다 충족되었음을 의미

 

---

 

## ✍️ 숫자 구성 방식

 

### 각 숫자는 \*\*$(n + m)$\*\*자리 10진수로 구성됨:

 

자리 번호	의미
1\~n번 자리	어떤 변수가 선택되었는지 표시 (딱 하나 선택해야 함)
n+1\~n+m번 자리	어떤 절이 만족되었는지 표시

---

 

### 예: 변수 $x_1$

 

* $x_1$이 True일 때 포함할 숫자:

 

 

100010

 

 

* $x_1$이 False일 때 포함할 숫자:

 

 

010000

 

 

→ 1번째 자리: $x_1$ 선택됨

→ 4번째 자리: 해당 절(절 1)을 만족시킴

 

---

 

## 목표 합 $T$ 설정

 

* 변수 자리: 합이 정확히 $n$이어야 함 (변수는 하나씩만 선택)

* 절 자리: 합이 ≥ 1이어야 하므로, 정확히 1로 세팅해서 강제

 

$$ T = \underbrace{111\ldots1}_{n} \underbrace{111\ldots1}_{m} $$

 

→ 합이 딱 $T$가 되려면:

 

* 변수는 정확히 1개씩만 선택돼야 하고

* 각 절은 **최소한 하나의 리터럴에 의해 참**이 돼야 함

 

---

 

##  반대로, 절이 만족되지 않으면?

 

* 절 자리에 1이 들어오지 않음

  → $T$를 절대 만들 수 없음

  → SUBSET SUM에서 **해 없음**

  → 3SAT 식도 **불만족**

 

---

 

## 예시 간단히 (초미니 버전)

 

### 3SAT 식:

 

$ (x_1 \lor x_2) \land (\neg x_1 \lor x_2) $

 

* 변수: $x_1, x_2$

* 절: $C_1, C_2$

 

→ 자리 수: 4자리

(1~~2번 = 변수 자리, 3~~4번 = 절 자리)

 

### 수 만들기 (2n = 4개):

 

| 변수 선택     | 수 (자리별 의미) |

| --------- | ---------- |

| $x_1 = T$ | 1 0 1 0    |

| $x_1 = F$ | 1 0 0 1    |

| $x_2 = T$ | 0 1 1 1    |

| $x_2 = F$ | 0 1 0 0    |

 

→ 목표합: $T = 1 1 1 1$

 

→ 올바른 부분집합만 이 목표합을 만들 수 있음

→ 즉, 3SAT 식 만족 ↔ 부분집합 존재

 

---

 

##  결론

 

> 이 환원은 논리식을 수학적 합으로 변환하면서도

> **정보 손실 없이 정확히 대응**시킨 구조의 예술적인 사례다.

 

→ 특히 **자리수 인코딩**과 **합 조건 = 논리 만족**이라는 점이 혁신적임

 

---

 

원하면:

 

* 위 예제를 수치 코드로 완전하게 정리해줄 수 있고

* 반대로 SUBSET SUM → SAT 환원 구조 분석도 가능해

 

어디로 가볼까?