# [08-06] 다항 시간 환원 (Polynomial-time Reduction)
다항 시간 환원은 한 문제를 다른 문제로 변환하는 방법으로, 문제들의 난이도를 비교하고 NP-완전을 증명하는 핵심 도구입니다.
🎯 환원이란 무엇인가
환원의 직관적 이해
환원(Reduction)은 어려운 문제를 이미 아는 문제로 바꿔서 푸는 것입니다.
실생활 비유:
상황: 외국어로 된 편지를 읽어야 함
어려운 방법: 외국어를 처음부터 배우기 → 몇 년 걸림
환원 방법:
1. 편지를 번역기에 넣기 (변환)
2. 한국어로 읽기 (이미 아는 문제 풀기)
3. 이해 완료!
핵심: 모르는 문제 → 아는 문제로 변환 → 해결프로그래밍 예시:
# 문제 A: 배열의 최댓값과 최솟값 차이는?
def range_of_array_hard(arr):
"""
직접 풀기: 어떻게 하지?
"""
pass
# 문제 B: 배열의 최댓값은? (이미 안다고 가정)
def max_of_array(arr):
"""max() 함수로 쉽게 풀 수 있음"""
return max(arr)
# 문제 C: 배열의 최솟값은? (이미 안다고 가정)
def min_of_array(arr):
"""min() 함수로 쉽게 풀 수 있음"""
return min(arr)
# 환원: A를 B와 C로 변환!
def range_of_array_easy(arr):
"""
환원을 사용한 해결
핵심 아이디어:
- "차이"는 "최댓값 - 최솟값"
- 최댓값, 최솟값은 이미 알고 있음
- 그러므로 문제 A를 B, C로 변환 가능!
단계:
1. 문제 A를 문제 B, C로 변환
2. 문제 B, C 각각 풀기 (쉬움!)
3. 결과 조합
"""
# 1단계: 입력 그대로 사용 (변환 없음)
# 2단계: B와 C 풀기
maximum = max_of_array(arr) # 문제 B
minimum = min_of_array(arr) # 문제 C
# 3단계: 결과 조합
result = maximum - minimum
return result
# 사용
arr = [3, 1, 4, 1, 5, 9, 2, 6]
print(f"범위: {range_of_array_easy(arr)}") # 9 - 1 = 8이것이 환원입니다! 모르는 문제를 아는 문제들로 바꿔서 푸는 것!
📐 다항 시간 환원의 정의
형식적 정의
기호: A ≤ₚ B
읽기: "A는 B로 다항 시간 환원된다"
의미: "B를 다항 시간에 풀 수 있으면 A도 다항 시간에 풀 수 있다"
즉:
- B가 쉬우면 A도 쉽다
- A가 어려우면 B도 어렵다환원의 3단계:
1단계: 입력 변환 (다항 시간)
A의 입력 → B의 입력
2단계: B 문제 풀기
B의 알고리즘 실행
3단계: 결과 변환 (다항 시간)
B의 답 → A의 답환원 예시 1: 독립 집합 → 클리크
두 문제 정의:
독립 집합 (Independent Set): k개 정점을 선택하되, 선택된 정점들끼리 간선이 없어야 함
예:
그래프: A-B, B-C (A와 B 연결, B와 C 연결)
k=2 독립 집합: {A, C} (A와 C는 연결 안 됨)
클리크 (Clique): k개 정점을 선택하되, 선택된 정점들끼리 모두 간선으로 연결되어야 함
예:
그래프: A-B, B-C, A-C (모두 연결)
k=3 클리크: {A, B, C} (모두 연결됨)환원 아이디어:
독립 집합의 "간선 없음"은 여집합 그래프의 "간선 있음"과 같습니다!
def independent_set_to_clique(graph, k):
"""
독립 집합 문제를 클리크 문제로 환원
핵심 아이디어:
- 원래 그래프에서 "연결 안 됨" = 여집합 그래프에서 "연결됨"
- 그러므로 원래 그래프의 독립 집합 = 여집합 그래프의 클리크
단계:
1. 그래프의 여집합 만들기 (다항 시간)
2. 여집합에서 k-클리크 찾기
3. 그 클리크 = 원래 그래프의 독립 집합
graph: 그래프 {정점: [이웃들]}
k: 찾을 정점 개수
Returns: 독립 집합 (클리크 문제로 풀어서)
"""
# 1단계: 입력 변환 (여집합 그래프 만들기)
complement = create_complement_graph(graph)
# 2단계: 클리크 문제 풀기 (여기서는 클리크 문제를 풀 수 있다고 가정)
clique = find_clique(complement, k)
# 3단계: 결과 변환 (여집합의 클리크 = 원래의 독립 집합)
independent_set = clique
return independent_set
def create_complement_graph(graph):
"""
그래프의 여집합 생성
여집합(Complement)이란?
- 원래 간선 있음 → 여집합 간선 없음
- 원래 간선 없음 → 여집합 간선 있음
- 즉, 간선 유무를 완전히 뒤집기!
왜 이렇게 하는가?
- 독립 집합: 간선 없는 정점들
- 클리크: 간선 있는 정점들
- 여집합에서 간선 관계가 반대가 되므로 독립 집합 ↔ 클리크 변환 가능!
시간복잡도: O(V²)
- 모든 정점 쌍을 확인해야 함
- V개 정점이면 V×V 쌍
- 다항 시간!
"""
# 1. 모든 정점 리스트 만들기
vertices = list(graph.keys())
# 2. 빈 여집합 그래프 초기화
complement = {}
for vertex in vertices:
complement[vertex] = []
# 3. 모든 정점 쌍 (v1, v2) 확인
for i in range(len(vertices)):
v1 = vertices[i]
# i+1부터 시작하는 이유:
# - 자기 자신과는 간선 만들지 않음 (v1-v1 같은 건 없음)
# - 이미 확인한 쌍은 건너뛰기 (v1-v2 확인했으면 v2-v1은 같음)
for j in range(i + 1, len(vertices)):
v2 = vertices[j]
# 원래 그래프에 v1-v2 간선이 없는가?
if v2 not in graph[v1]:
# 없으면 여집합에는 있어야 함!
complement[v1].append(v2)
complement[v2].append(v1) # 양방향 간선
return complement
# ===== 사용 예시 =====
# 원래 그래프
graph = {
'A': ['B'], # A-B만 연결
'B': ['A', 'C'], # B-C도 연결
'C': ['B'],
'D': [] # D는 독립
}
print("원래 그래프:")
print(" 간선: A-B, B-C")
print(" D는 독립적")
# 여집합 그래프 만들기
complement = create_complement_graph(graph)
print("여집합 그래프:")
print(f" {complement}")
print(" 원래 없던 간선들만 있음!")
# 독립 집합 {A, C, D}는 여집합에서 클리크가 됨!
print("분석:")
print(" 원래: A와 C는 연결 안 됨 (독립)")
print(" 여집합: A와 C는 연결됨 (클리크)")환원 시간 복잡도:
1단계: 여집합 만들기 = O(V²)
2단계: 클리크 찾기 = 클리크 알고리즘 시간
3단계: 결과 변환 = O(1)
총: O(V²) + 클리크 시간 → 다항 시간 환원!🔗 환원의 성질
성질 1: 추이성 (Transitivity)
추이성은 "A → B이고 B → C이면 A → C"라는 성질입니다.
만약:
- A ≤ₚ B (A를 B로 환원 가능)
- B ≤ₚ C (B를 C로 환원 가능)
그러면: A ≤ₚ C (A를 C로 환원 가능)
비유: 번역과 같음
- 한국어 → 영어 번역 가능
- 영어 → 프랑스어 번역 가능
→ 한국어 → 프랑스어 번역 가능 (영어 거쳐서)코드 예시:
def transitivity_example():
"""
환원의 추이성 예시
문제 A: 배열 정렬되어 있는가?
문제 B: 배열 정렬하기
문제 C: 배열 병합하기 (정렬된 두 배열)
환원:
A ≤ₚ B: 정렬해서 비교
B ≤ₚ C: 병합 정렬 사용
추이성: A ≤ₚ C: A를 C로 직접 환원 가능
"""
# A ≤ₚ B: A를 B로 환원
def is_sorted_via_sort(arr):
"""
정렬되어 있는가? (정렬 이용)
"""
sorted_arr = sort_array(arr) # B 문제 사용
return arr == sorted_arr
# B ≤ₚ C: B를 C로 환원
def sort_array(arr):
"""
정렬하기 (병합 이용)
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = sort_array(arr[:mid])
right = sort_array(arr[mid:])
return merge_arrays(left, right) # C 문제 사용
# C 문제: 병합
def merge_arrays(left, right):
"""정렬된 두 배열 병합"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 추이성: A ≤ₚ C
# A를 푸는데 B를 거쳐 C를 사용 → A를 C로 직접 환원한 것과 같음
arr = [1, 2, 3, 4, 5]
print(f"정렬됨? {is_sorted_via_sort(arr)}")
transitivity_example()성질 2: 방향성
환원은 방향이 있습니다.
A ≤ₚ B이지만 B ≤ₚ A는 아닐 수 있음
예: 정렬 여부 확인 ≤ₚ 정렬 (정렬할 수 있으면 확인도 가능)
하지만: 정렬 ≤ₚ 정렬 여부 확인 (✗) (확인만 할 수 있다고 정렬할 수 있는 건 아님)
비유: 읽기 ≤ₚ 쓰기 (쓸 수 있으면 읽을 수 있음)
하지만 쓰기 ≤ₚ 읽기 (✗) (읽을 수 있다고 쓸 수 있는 건 아님)성질 3: NP-완전 증명에 사용
NP-완전 증명 방법:
문제 X가 NP-완전임을 증명하려면:
1단계: X ∈ NP 증명 → 다항 시간 검증자 만들기
2단계: 알려진 NP-완전 Y 선택 → 예: SAT, 클리크, 해밀턴 경로
3단계: Y ≤ₚ X 증명 → Y를 X로 다항 시간 환원
결론: X는 NP-완전!💡 실무 팁
환원 설계 전략
전략 1: 유사한 구조 찾기
def find_reduction_strategy(problem_A, problem_B):
"""
두 문제 사이의 환원 찾기
체크리스트:
1. 입력이 비슷한가?
- 둘 다 그래프?
- 둘 다 수열?
2. 제약 조건이 비슷한가?
- 둘 다 "선택" 문제?
- 둘 다 "연결성" 문제?
3. 변환이 간단한가?
- 간선 추가/제거?
- 정점 추가/제거?
4. 여집합/반대 개념인가?
- 독립 집합 ↔ 클리크
- 최대 ↔ 최소
"""
pass전략 2: 가젯(Gadget) 사용
가젯: 작은 구조를 조합해서 큰 구조 만들기
예: SAT → 해밀턴 경로
1. 각 변수 → 작은 그래프 (가젯)
2. 각 절 → 연결 구조 (가젯)
3. 조합 → 전체 그래프
장점: 복잡한 변환을 단순한 부품으로환원 검증 방법
def verify_reduction(A_input, B_input, A_solver, B_solver):
"""
환원이 올바른지 검증
확인 사항:
1. A의 Yes 입력 → B의 Yes 입력
2. A의 No 입력 → B의 No 입력
3. 변환 시간이 다항인가?
A_input: 문제 A의 입력
B_input: A_input을 변환한 B의 입력
A_solver: A를 푸는 (가상의) 함수
B_solver: B를 푸는 함수
"""
# A의 답
A_answer = A_solver(A_input)
# B의 답
B_answer = B_solver(B_input)
# 같아야 함!
if A_answer == B_answer:
print("✓ 환원 올바름")
return True
else:
print("✗ 환원 잘못됨")
return False🎯 핵심 정리
다항 시간 환원
정의: A ≤ₚ B 즉 "A를 B로 다항 시간에 변환 가능"
의미:
- B를 풀 수 있으면 A도 풀 수 있음
- B가 쉬우면 A도 쉬움
- A가 어려우면 B도 어려움환원의 3단계
1. 입력 변환 (다항 시간)
A의 입력 → B의 입력
2. B 문제 풀기
B의 알고리즘 실행
3. 결과 변환 (다항 시간)
B의 답 → A의 답환원의 성질
추이성: A ≤ₚ B이고 B ≤ₚ C이면 A ≤ₚ C
방향성: A ≤ₚ B이지만 B ≤ₚ A는 아닐 수 있음
NP-완전 증명: 알려진 NP-완전 Y에서 새 문제 X로 환원 → X도 NP-완전실무 활용
1. 문제 난이도 비교
2. NP-완전 증명
3. 알고리즘 재사용
4. 복잡한 문제를 알려진 문제로 변환🔗 다음 글에서는
[08-07] 계산 불가능성 (Undecidability)
- 계산 불가능성의 정의: 컴퓨터로 절대 풀 수 없는 문제들
- 결정 가능 vs 불가능: 튜링 기계의 한계
- 대표 예시: 정지 문제, 타일링 문제
- 환원으로 불가능성 증명: 정지 문제를 다른 문제로 환원
이전 글: [08-05] NP-난해
다음 글: [08-07] 계산 불가능성
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자