3-SAT → k-Clique

좋습니다 😎그럼 이번에는 직접 해볼만한 워밍업 환원 문제 드려볼게요:🎯 환원 워밍업: 3-SAT → k-Clique이건 실제로 Karp의 21문제 중 대표 환원이자환원 훈련의 가장 클래식한 예시 중 하나입니다.💡 목표주어진 3-SAT 인스턴스를 받아“이것을 만족하는 해가 존재하는가?” ⟶그에 대응하는 k-Clique이 있는 그래프를 구성하라.🧱 아이디어 구조3-SAT 인스턴스:(x1∨¬x2∨x3)∧(¬x1∨x2∨¬x3)∧(⋯ )(x_1 \lor \neg x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor \neg x_3) \land (\cdots)→ 각 절(clause)당 3개의 리터럴 존재절마다 3개의 노드를 생성 (총 3×m3 \times m개의 노드)다른 절에 속한..

환원 난이도 순위표

좋아, 너가 고른 **“환원 난이도 순위표”** —즉, **이론적으로는 환원이 가능하지만 구조적 궁합이나 변환 난이도 측면에서 얼마나 힘든지**를직관적으로 비교한 정리표를 만들어볼게. --- ## 🎯 기준: 환원 “난이도” = 이론 가능성은 같지만, **직관적 대응, 표현 구조, 제약 정렬, 수식 복잡도, 시각화 난이도** 등을 고려한 실제 환원 설계의 어려움 --- ## 🔥 NP-완전 문제 환원 난이도 순위표 | 난이도 등급 | 환원 예시 | 이유 ..

Hamiltonian Cycle ↔ TSP

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

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

Turing Halt Problerm

k-Clique Problem

SAT

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₂ 노드 조합 중..

Partition Problem

부분집합 A의 합=전체 합/2. 즉, Subset Sum 문제에서 목표 합 K = total/2로 두고 풀면 Partition 문제와 동일하다. S={3,1,1,2,2,1}합 T=10T = 10T=10 → 짝수 → 목표: Subset 합 = 5가능한 부분집합: {3, 2}, {1,1,2,1} 등→ Subset Sum 문제로 변환 완료

Subset Sum / Knapsack

Subset Sum: NP완전에서 아주 직관적인 문제중 하나다. 집합의 부분집합 중에서 그 합이 0인 경우가 존재하면 참이 된다 {-1, 3, -2, 4} -1+3-2=0 이 집합은 참이다. 부분집합의 합이 0이 아니라 특정 수로 정하면 Knapsack 문제가 된다.Knapsack: 배낭의 용량이 C이고, n개의 물건의 각각의 무게와 가치가 주어질 때, 배낭에 담을 수 있는 최대 가치를 찾는 문제print("fsd")

Planar 3-SAT

간선이 서로 겹치지 않고 그려질 수 있는가의 문제. ​

Exact Cover

A = {1, 4, 7};B = { 1 , 4 };C = {4, 5, 7};D = { 3 , 5 , 6 };E = {2, 3, 6, 7}; 그리고F = { 2 , 7 }.A가 선택되면 B의 원소 1과 교집합이 생기므로 B는 선택될 수 없다. B를 선택할때는 A를 선택할 수 없다. { B , D , F }는 유일한 Exact Cover 이다.

3-D Matching

X, Y, Z 가 겹치지 않게 묶여진 집합의 수가 K 개를 만족시키면 OK

NP-Complete

3-SAT3-충족 가능성 문제(3-SAT, Boolean satisfiability problem)는 NP-완전의 대표주자이고 모든 문제 환원의 기준이다. 이 문제는 참 또는 거짓의 진리 값을 가질 수 있는 3개의 문자 또는 변수 p,q,r 이 있다. 그리고 논리합으로 연결된 절 몇 개가 논리곱으로 구성된 부울 수식 f가 참이 되도록 문자의 진리 값을 구할 수 있는가를 묻는다.Hamiltonian Path / CycleHamiltonian Path: 그래프의 모든 정점을 한번씩 방문하는 알고리즘Hamiltonian Cycle: 시작점과 끝점이 동일한 헤밀턴 경로Graph Coloring그래프의 각 정점에 같은 색깔이 인접하지 않게 칠하는 방법이다. 이것으로 그래프의 불변성을 정의할 수 있다.Vertex ..

P=NP? P≠NP?

P 대 NP 문제에 대한 정확한 설명은 Stephen Cook 이 그의 선구적 논문 “The Complexity of Theorem‑Proving Procedures” (1971) 과 같은 시기에 러시아 학자인 Leonid Levin 논문으로 부터 출발했다. Cook-Levin 정리 발표 이후 Richard Karp가 “Reducibility Among Combinatorial Problems” (1972) 논문을 통해 21가지 문제가 NP-완전임을 증명하였다. P=NP는 모든 NP 문제를 P 문제처럼 다항 시간 안에 해결할 수 있는지를 묻는 문제이다. 클래스 P는 결정론적 튜링 기계로 다항 시간 안에 해를 찾을 수 있는 문제들의 집합이고, NP는 해답이 주어졌을 때 그 해를 다항 시간 안에 검증할 수..