좋아, 너가 고른 **“환원 난이도 순위표”** —
즉, **이론적으로는 환원이 가능하지만 구조적 궁합이나 변환 난이도 측면에서 얼마나 힘든지**를
직관적으로 비교한 정리표를 만들어볼게.
---
## 🎯 기준: 환원 “난이도” = 이론 가능성은 같지만,
**직관적 대응, 표현 구조, 제약 정렬, 수식 복잡도, 시각화 난이도** 등을 고려한 실제 환원 설계의 어려움
---
## 🔥 NP-완전 문제 환원 난이도 순위표
| 난이도 등급 | 환원 예시 | 이유 |
| --------------------- | ------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------- |
| 🟩 **매우 쉬움** | **3SAT → CLIQUE**<br>**CLIQUE ↔ VERTEX COVER**<br>**PARTITION ↔ SUBSET SUM** | - 구조 1:1 대응<br>- 변수 ↔ 노드 / 집합<br>- 간선 ↔ 모순 회피 / 충족 조건<br>- 시각화 쉬움 |
| 🟨 **중간 난이도** | **3SAT → SUBSET SUM**<br>**3SAT → TSP**<br>**TSP ↔ Hamiltonian Cycle** | - 표현은 다르지만<br>- 자리수/비용 등을 통해 논리 구조를 잘 encode 가능<br>- 다만 설계는 조작 필요 |
| 🟧 **어려움** | **3SAT → Exact Cover / X-COVER**<br>**3SAT → 3D Matching**<br>**3SAT → ILP (0-1 Integer Linear Programming)** | - 논리 ↔ 조합/계산 구조이긴 하지만<br>- 해 표현이 늘어나고 중간 계산 많음<br>- 설계 시 변수 폭발 위험 |
| 🟥 **매우 어려움 (궁합 최악)** | **3SAT → TILING**<br>**3SAT → GEOMETRIC COVER**<br>**3SAT → BIN PACKING**<br>**3SAT → SCHEDULING** | - 논리 → 공간/시간/구간으로 억지 변환<br>- 직관적 대응 거의 없음<br>- 수공예적 환원<br>- 완전한 시뮬레이션이 필요함 (가젯 기반) |
---
## 🔧 가젯 기반 환원이 뭐냐면?
* 예: 3SAT → TILING 할 때,
* **변수 가젯**: 진리값을 타일 방향으로 표현
* **절 가젯**: 세 변수가 모두 특정 방향일 때만 타일이 들어맞게
* **와이어 가젯**: 변수를 절로 "신호"처럼 전달
> 이건 말 그대로 **논리회로를 타일로 만드는 작업**이야
> (즉, 논리식을 공간으로 완전 시뮬레이션)
---
## 👑 가장 환원 난이도 높은 조합들
1. **3SAT → TILING**
2. **3SAT → 3D TETROMINO PACKING**
3. **3SAT → GEOMETRIC INTERVAL COVER**
4. **3SAT → RESOURCE-CONSTRAINED SCHEDULING**
---
## 🎓 정리
> 환원은 이론적으로 다항시간에 가능해도,
> **구조적 궁합이 틀어지면 난이도는 수공예 지옥으로 상승한다.**
---
필요하면 이걸 시각화해서 **문제 간 환원 궁합 맵**으로 그려줄 수도 있어.
예: 노드 = 문제, 간선 = 환원, 색 = 난이도.
해볼까?