Hamiltonian Cycle ↔ TSP

이 환원은 정말 구조가 완벽하게 맞아떨어지는 대표적인 NP-완전 ↔ NP-완전 환원이고,문제 간의 핵심 구조가 거의 1:1로 대응되기 때문에이걸 보면 NP-완전 환원이 단순한 문제가 아니라는 걸 직관적으로 깨닫게 된다. --- 목적 * Hamiltonian Cycle: → 그래프에서 모든 정점을 정확히 한 번씩 방문하고 처음으로 돌아오는 경로가 존재하는가? * TSP (결정판): → 주어진 거리 행렬이 있을 때, 모든 도시를 한 번씩 방문하는 순회 경로의 총 비용이 B 이하인가? --- 환원 개요: > Hamiltonian Cycle 문제를 → TSP 문제로 환원> → 즉, 순수한 "존재 여부" 문제를> → 비용 조건이 붙은 최적화 문제 형태로 바꾸는 것. --- 환원 과정 요약 입력: 무방향 그래프..

• format_list_bulleted Reduction
• · 2025. 6. 30.

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, ...

• format_list_bulleted Reduction
• · 2025. 6. 30.

3-SAT <-> Clique

3-SAT -> Clique 환원F=(x1​∨¬x2​∨x3​)∧(¬x1​∨x2​∨¬x3​)환원 단계 요약 아이디어:각 절에서 하나씩 리터럴을 선택하되,모순이 없는 조합끼리만 간선을 연결→ 그런 간선들로 클릭(K) 크기의 완전 그래프가 존재하면 만족 가능Step 1. 절마다 리터럴 → 노드 만들기노드 이름 내용절 번호v₁x1​C₁v₂¬x2C₁v₃x3C₁v₄¬x1C₂v₅x2C₂v₆¬x3C₂총 6개의 노드를 만들었다.각 노드는 어느 절에서 어떤 리터럴인지 기억하고 있음.Step 2. 간선 연결 규칙다음 조건을 만족할 때만 간선을 연결한다.1. 두 노드가 다른 절에서 나왔을 것2. 두 리터럴이 모순되지 않을 것 (예: \(x_1​ \text{ vs } \neg x_1\) 절 C₁ 노드 ↔ 절 C₂ 노드 조합 중..

• format_list_bulleted Reduction
• · 2025. 6. 28.