토픽 39 / 82

NP 완전 (NP-Complete)

다항 시간 내에 해를 검증할 수 있지만(NP) 다항 시간 알고리즘이 알려지지 않은 가장 어려운 문제 부류로, 모든 NP 문제가 다항 시간에 환원 가능

목적: 문제 난이도 분류, 알고리즘 한계 이해, 근사·휴리스틱 필요성

특징: NP-hard + NP, 다항 시간 미발견, 모든 NP 환원 가능

복잡도 클래스

P vs NP 문제: P = NP? (미해결, 밀레니엄 문제)

환원(Reduction): 문제 A를 문제 B로 변환, A ≤ B

주요 NP-완전 문제: SAT(Boolean Satisfiability, 첫 NP-완전), 외판원(TSP), 배낭(0-1 Knapsack), 그래프 색칠, 해밀턴 경로, 부분집합 합

대응 방법: 근사 알고리즘, 휴리스틱, 메타 휴리스틱(유전 알고리즘, 시뮬레이티드 어닐링), 특수 케이스, 지수 시간 허용

장점: 문제 난이도 이해, 최적화 포기 정당화, 연구 방향

단점: 다항 시간 해 없음(추정), 실용적 해결 어려움

적용사례: 스케줄링, 자원 할당, 회로 설계, 암호학, 물류

비교: P(빠름) vs NP(검증빠름) vs NP-complete(가장어려움) vs NP-hard(검증 조건없음)

연관: P vs NP, SAT, TSP, 배낭 문제, 근사 알고리즘