복잡도 클래스(Complexity Classes)는 계산 문제를 풀거나 검증하는 데 필요한 자원(시간·공간)에 따라 분류한 집합이다. P, NP, PSPACE 등이 주요 클래스다.
주요 복잡도 클래스
| 클래스 | 정의 | 예시 문제 |
|---|
| P | 결정론적 TM, 다항 시간 | 정렬, 최단경로 |
| NP | 비결정론적 TM, 다항 시간 | SAT, 클릭 |
| co-NP | NP의 여집합 | 동어 반복 확인 |
| NP-Hard | 모든 NP 문제가 환원 가능 | 정지 문제 |
| NP-Complete | NP ∩ NP-Hard | 3-SAT, TSP 결정 |
| PSPACE | 다항 공간, 무제한 시간 | TQBF |
| EXPTIME | 지수 시간 | 체스 최적 수 |
계층 관계
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME
알려진 엄격한 포함관계:
P ⊊ EXPTIME (시간 계층 정리로 증명됨)
NP ⊊ NEXPTIME
P ⊊ PSPACE (추정, 미증명)
환원(Reduction)
다항 시간 환원 A ≤ₚ B:
문제 A를 B로 다항 시간 내에 변환 가능하면
B를 풀 수 있으면 A도 풀 수 있다
3-SAT ≤ₚ 클릭 문제 ≤ₚ 정점 커버 ≤ₚ 해밀턴 순환
쿡-레빈 정리:
SAT는 NP-완전
(모든 NP 문제는 SAT로 환원 가능)
공간 복잡도 클래스
L : O(log n) 공간 (결정론적)
NL : O(log n) 공간 (비결정론적)
PSPACE: 다항 공간
Savitch 정리: NSPACE(f(n)) ⊆ DSPACE(f(n)²)
→ NL ⊆ DSPACE(log²n)
→ NPSPACE = PSPACE
근사 알고리즘
NP-완전 문제에 대한 현실적 대응.
ρ-근사 알고리즘: 최적해의 ρ배 이내 해 보장
정점 커버: 2-근사 알고리즘 존재
TSP (삼각 부등식 만족 시): 1.5-근사 (Christofides)
일반 TSP: 근사 불가능 (P≠NP 가정 시)
관련 개념
