# [08-05] NP-난해 (NP-Hard)
NP-난해는 적어도 NP-완전만큼 어려운 문제들의 집합으로, NP에 속할 필요가 없는 더 일반적인 개념입니다.
🎯 NP-난해란 무엇인가
NP-난해의 정의
NP-난해(NP-Hard)는 적어도 NP-완전만큼 어려운 문제들입니다.
쉬운 비유:
게임 난이도로 비유하면:
쉬움 (P 문제):
- 누구나 클리어 가능
- 시간 들이면 풀림
- 예: 퍼즐 맞추기
어려움 (NP 문제):
- 답 확인은 쉬움
- 찾기는 어려움
- 예: 스도쿠 (확인은 쉬움)
최고 난이도 (NP-완전):
- NP 중 가장 어려움
- 하나만 풀면 다 풀림
- 예: 스도쿠 풀기
초월 난이도 (NP-난해):
- NP-완전만큼 또는 더 어려움
- 답 확인도 어려울 수 있음
- 예: "최적의 스도쿠 전략은?" (답 확인도 어려움)핵심 차이:
NP-완전:
1. NP에 속함 ✓
→ 답을 빠르게 확인할 수 있음
2. 매우 어려움 ✓
NP-난해:
1. NP에 속함 ? (필수 아님!)
→ 답 확인도 어려울 수 있음
2. 매우 어려움 ✓
즉:
모든 NP-완전은 NP-난해
하지만 모든 NP-난해가 NP-완전은 아님!📊 복잡도 클래스 관계
전체 그림
전체 문제들
┌─────────────────────┐
│ NP-난해 │ ← 매우 어려운 문제들
│ ┌──────────────┐ │
│ │ NP │ │ ← 확인은 쉬운 문제들
│ │ ┌──────────┐ │ │
│ │ │ NP-완전 │ │ │ ← NP 중 가장 어려움
│ │ │ ┌────┐ │ │ │
│ │ │ │ P │ │ │ │ ← 풀기도 쉬운 문제들
│ │ │ └────┘ │ │ │
│ │ └──────────┘ │ │
│ └──────────────┘ │
│ NP-난해이지만 │
│ NP는 아닌 문제들: │
│ - 정지 문제 │
│ - 최적화 문제들 │
└─────────────────────┘
포함 관계:
P ⊆ NP
NP-완전 ⊆ NP
NP-완전 ⊆ NP-난해 ← 주목!🔍 결정 문제 vs 최적화 문제
왜 최적화 문제는 NP-난해인가?
핵심 아이디어:
결정 문제는 Yes/No로 답하지만, 최적화 문제는 "최선의 답"을 찾아야 합니다. 그리고 그것이 정말 최선인지 증명하기가 어렵습니다.
결정 문제:
"1000km 이하 경로가 있나?"
→ Yes/No 답
→ 경로 하나만 주면 확인 가능 (거리 계산해서 비교)
→ 다항 시간 검증 ✓
→ NP에 속함
최적화 문제:
"최단 경로는?"
→ 숫자 답 (예: 850km)
→ 이것이 최단인지 어떻게 증명?
→ 다른 모든 경로를 확인해야만 "최단"임을 알 수 있음
→ 다항 시간 검증 ✗
→ NP에 속하지 않음!예시: 외판원 문제
def tsp_optimization(cities, distances):
"""
외판원 최적화 문제
문제: 최단 순회 경로와 그 거리는?
이것이 NP-난해인 이유:
- 누군가 "850km가 최단"이라고 주장해도
- 정말 최단인지 증명하려면 모든 경로를 확인해야 함
- 다항 시간에 검증 불가능
- 따라서 NP에 속하지 않음
cities: 도시 리스트
distances: 거리 행렬 distances[i][j] = i에서 j까지 거리
Returns: (최단_경로, 최단_거리)
"""
import itertools # 데이터의 순열, 조합, 반복 같은 복잡한 계산을 직접 for문으로 짜지 않고도 매우 빠르고 메모리 효율적으로 처리
n = len(cities)
# 최단 거리를 추적 (처음엔 무한대로 초기화)
min_distance = float('inf') # float('inf')는 "무한대"를 의미
best_tour = None
# 모든 순열(permutation) 확인
# itertools.permutations: 모든 순서 조합을 생성 # 예: [0,1,2] → (0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1), (2,1,0)
for perm in itertools.permutations(range(n)):
# perm: 도시 방문 순서 # 예: (0, 2, 1, 3) = 도시0 → 도시2 → 도시1 → 도시3 → 도시0
# 이 경로의 총 거리 계산
distance = 0
for i in range(n):
from_city = perm[i] # 현재 도시
# 다음 도시 (마지막 도시 다음은 첫 도시로 돌아감)
to_city = perm[(i + 1) % n] # % 연산자는 나머지
# 거리 누적
distance += distances[from_city][to_city]
# 더 짧은 경로를 발견했는가?
if distance < min_distance:
min_distance = distance
best_tour = perm
return best_tour, min_distance
# ===== 사용 예시 =====
cities = ['서울', '부산', '대구', '광주']
distances = [
# 서울 부산 대구 광주
[ 0, 400, 300, 250], # 서울에서
[ 400, 0, 150, 300], # 부산에서
[ 300, 150, 0, 200], # 대구에서
[ 250, 300, 200, 0] # 광주에서
]
tour, dist = tsp_optimization(cities, distances)
print(f"최단 경로: {[cities[i] for i in tour]}")
print(f"총 거리: {dist}km")검증의 어려움:
누군가 "900km가 최단 거리"라고 주장하면, 정말 최단인지 확인하려면 어떻게 해야 할까요?
위 코드처럼 모든 경로를 다 확인해야만 합니다:
- 4개 도시: 3! = 6가지 경로 (작아서 가능)
- 10개 도시: 9! = 362,880가지
- 20개 도시: 19! = 121,645,100,408,832,000가지 (불가능!)
다항 시간에 검증할 수 없으므로, NP에 속하지 않습니다. 따라서 NP-난해입니다.
📋 NP-난해 문제 예시
예시 1: 배낭 최적화
def knapsack_optimization(items, capacity):
"""
배낭 최적화 문제 (초보자용 상세 설명)
문제:
- 배낭 용량: capacity (예: 50kg)
- 물건들: [(무게, 가치), ...]
- 질문: 최대 가치는?
핵심 아이디어: 각 물건에 대해 "넣는다" 또는 "안 넣는다" 두 가지 선택 → n개 물건이면 2^n 가지 조합
예: 3개 물건
- 조합 1: 아무것도 안 넣음
- 조합 2: 물건 0만
- 조합 3: 물건 1만
- 조합 4: 물건 0, 1
- ...
- 조합 8: 물건 0, 1, 2 모두 총 2³ = 8가지
비트로 표현하는 이유:
각 물건의 선택 여부를 0/1로 표현하면 편리함 예: 101(이진수) = 물건 0과 2를 선택
items: 물건 리스트, 각 물건은 (무게, 가치)
capacity: 배낭의 최대 용량
Returns: (최대_가치, 선택한_물건_인덱스들)
"""
n = len(items) # 물건 개수
# 최대 가치 추적
max_value = 0
best_subset = []
# ===== 핵심: 모든 부분집합을 비트로 표현 =====
#
# 왜 range(2^n)인가? 각 물건마다 "넣음/안넣음" 2가지 선택
# → n개 물건이면 2 × 2 × ... × 2 = 2^n 가지
#
# 예: n=3이면
# 0 = 000(이진) = 아무것도 안 넣음
# 1 = 001(이진) = 물건 0만
# 2 = 010(이진) = 물건 1만
# 3 = 011(이진) = 물건 0, 1
# 4 = 100(이진) = 물건 2만
# 5 = 101(이진) = 물건 0, 2
# 6 = 110(이진) = 물건 1, 2
# 7 = 111(이진) = 물건 0, 1, 2 모두
total_combinations = 2 ** n
# 모든 조합 시도
for i in range(total_combinations): # i를 이진수로 해석해서 부분집합 만들기
# 예: i=5, n=3이면, 5 = 101(이진수) → 물건 0(첫 번째 비트=1), 물건 2(세 번째 비트=1) 선택
subset = [] # 선택한 물건들
total_weight = 0 # 총 무게
total_value = 0 # 총 가치
# 각 물건(j)에 대해 i의 j번째 비트가 1인지 확인
for j in range(n):
# ===== 비트 연산 상세 설명 =====
#
# (1 << j): 1을 왼쪽으로 j칸 이동 → j번째 비트만 1인 숫자 만들기
#
# 예:
# j=0: 1 << 0 = 1 = 001(이진)
# j=1: 1 << 1 = 2 = 010(이진)
# j=2: 1 << 2 = 4 = 100(이진)
#
# i & (1 << j): i의 j번째 비트가 1인가?
# → &는 AND 연산 (둘 다 1이어야 1)
#
# 예: i=5=101(이진)일 때
# j=0: 101 & 001 = 001 (0이 아님) → True
# j=1: 101 & 010 = 000 (0) → False
# j=2: 101 & 100 = 100 (0이 아님) → True
#
# 즉, j번째 비트가 1이면 물건 j를 선택!
if i & (1 << j): # j번째 비트가 1인가?
# 이 물건을 선택!
subset.append(j)
total_weight += items[j][0] # 무게 추가
total_value += items[j][1] # 가치 추가
# 이 조합이 용량 이내이고, 가치가 더 큰가?
if total_weight <= capacity and total_value > max_value:
max_value = total_value
best_subset = subset
return max_value, best_subset
# ===== 사용 예시와 비트 연산 이해하기 =====
items = [
(10, 60), # 물건 0: 무게 10kg, 가치 60
(20, 100), # 물건 1: 무게 20kg, 가치 100
(30, 120), # 물건 2: 무게 30kg, 가치 120
]
capacity = 50
# 비트 연산이 어떻게 작동하는지 확인
print("=== 비트 연산 작동 방식 ===\n")
# 예: i=5일 때 (101 이진수)
i = 5
print(f"i = {i} = {bin(i)} (이진수)")
print(f"물건 개수: {len(items)}개\n")
for j in range(len(items)):
bit_mask = 1 << j # j번째 비트만 1
result = i & bit_mask # AND 연산
print(f"물건 {j} 확인:")
print(f" (1 << {j}) = {bit_mask:3d} = {bin(bit_mask):>5s}")
print(f" {i} & {bit_mask} = {result:3d} = {bin(result):>5s}")
if result:
print(f" → 물건 {j} 선택! (비트가 1)")
else:
print(f" → 물건 {j} 제외 (비트가 0)")
print()
# 실제 함수 실행
max_val, selected = knapsack_optimization(items, capacity)
print("=== 최종 결과 ===")
print(f"최대 가치: {max_val}")
print(f"선택한 물건: {selected}")
print(f"세부 정보: {[items[i] for i in selected]}")검증의 어려움:
"최대 가치 220"이라는 답을 검증하려면:
- 3개 물건: 2³ = 8가지 조합 (가능)
- 30개 물건: 2³⁰ = 1,073,741,824가지 (불가능!)
모든 조합을 확인해야 최대인지 알 수 있으므로, 다항 시간 검증이 불가능합니다.
예시 2: 정지 문제 (더 어려움!)
정지 문제는 NP-난해보다 훨씬 더 어렵습니다. 사실 컴퓨터로 절대 풀 수 없는 문제입니다!
문제:
주어진 프로그램이 특정 입력에 대해
- 정지하는가? (끝나는가?)
- 무한 루프인가? (영원히 안 끝나는가?)난이도: 결정 불가능(Undecidable) - 어떤 알고리즘으로도 풀 수 없음!
# 예시 1: 명백히 정지하는 프로그램
def program1(n):
"""입력 받고 바로 종료"""
return n + 1
# → 명백히 정지함!
# 예시 2: 명백히 안 끝나는 프로그램
def program2(n):
"""무한 루프"""
while True:
pass
# → 명백히 정지 안 함!
# 예시 3: 모르는 경우 (콜라츠 추측)
def collatz(n):
"""
콜라츠 추측:
- 짝수면 2로 나누기
- 홀수면 3배 더하기 1
- 1이 될 때까지 반복
"""
while n != 1:
if n % 2 == 0: # 짝수
n = n // 2
else: # 홀수
n = 3 * n + 1
return True
# collatz(5): 5 → 16 → 8 → 4 → 2 → 1 (정지!)
# collatz(6): 6 → 3 → 10 → 5 → ... → 1 (정지!)
#
# 질문: 모든 양수 n에 대해 정지하는가?
# → 아무도 모름! (90년 이상 미해결)
# → n=1조까지는 정지함이 확인됨
# → 하지만 모든 n에 대해서는?정지 문제의 불가능성:
튜링이 1936년에 증명한 사실: 어떤 알고리즘으로도 모든 프로그램에 대해 정지 여부를 판단할 수 없습니다.
이것이 의미하는 것:
- 완벽한 바이러스 검사: 불가능
- 완벽한 디버거: 불가능
- 프로그램 무한 루프 자동 탐지: 불가능
난이도 순서:
P < NP < NP-완전 < NP-난해 < 정지 문제 (결정 불가능)🔧 NP-완전과 NP-난해 비교
핵심 차이점
NP에 속함? 검증 가능? 문제 형태 예시
----------------------------------------------------------------
NP-완전 ✓ ✓ (다항) 결정(Yes/No) SAT, 클리크
NP-난해 ? ? (어려움) 모든 형태 TSP최적화, 정지 문제
관계:
모든 NP-완전 → NP-난해
일부 NP-난해 → NP-완전 아님결정 vs 최적화 (같은 문제):
# NP-완전: TSP 결정 문제
def tsp_decision(cities, distances, max_distance):
"""
질문: max_distance 이하 경로가 있나?
답: Yes/No
검증: 경로 주면 O(n)에 확인 가능
→ NP에 속함 → NP-완전
"""
pass
# NP-난해: TSP 최적화 문제
def tsp_optimization(cities, distances):
"""
질문: 최단 경로는?
답: 경로 + 거리
검증: 최단임을 증명하려면 모든 경로 확인 → NP에 속하지 않음 → NP-난해
"""
pass🎯 핵심 정리
NP-난해란?
정의: 적어도 NP-완전만큼 어려운 문제들
특징:
1. NP에 속할 필요 없음 → 검증이 어려울 수 있음
2. 결정 문제가 아닐 수도 있음 → 최적화, 계산 문제 포함
3. 매우 어려움 → 효율적 알고리즘 없을 가능성NP-완전 vs NP-난해
NP-완전:
- NP에 속함 ✓
- 검증 다항 시간 ✓
- 결정 문제 (Yes/No)
- 예: SAT, 클리크, 해밀턴 경로
NP-난해:
- NP에 속함 ? (선택사항)
- 검증 어려울 수 있음
- 모든 형태 가능
- 예: TSP 최적화, 배낭 최적화, 정지 문제
관계: NP-완전 ⊂ NP-난해왜 최적화 문제는 NP-난해인가?
결정 문제:
"1000km 이하 경로 있나?"
→ 경로 하나만 확인 → O(n)
→ 다항 시간 검증 ✓
→ NP
최적화 문제:
"최단 경로는?"
→ 모든 경로 확인해야 최단 증명
→ O(n!) 시간 필요
→ 다항 시간 검증 ✗
→ NP 아님 → NP-난해실무 대응
NP-난해 문제를 만나면:
1. 근사 알고리즘 사용 → 최적의 90% 정도 찾기
2. 휴리스틱 사용 → 경험적 방법 (보장 없지만 실전 OK)
3. 문제 완화 → 제약 조건 줄이기
4. 작은 입력만 처리 → 정확한 해 구하기🔗 다음 글에서는
[08-06] 다항 시간 환원 (Polynomial-time Reduction)
- 환원의 형식적 정의: Karp 환원과 Cook 환원의 차이
- 환원의 성질: 추이성, 방향성, 닫힘 성질
- 환원 예시: 다양한 NP-완전 문제들 간의 환원 과정
- 환원 활용: 새로운 NP-완전 문제를 증명하는 방법
이전 글: [08-04] NP-완전
다음 글: [08-06] 다항 시간 환원
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자