[CS300 #080] P·NP·NP-완전 — 찾기는 어렵고 확인은 쉬운 문제들
컴퓨터공학 300 주제 시리즈의 080번째 글이다. 전체 지도는 여기.
한 줄 요약
P 는 다항 시간에 풀 수 있는 판정 문제의 모임이고, NP 는 답이 “예” 일 때 그 증거를 다항 시간에 확인할 수 있는 문제의 모임이다. NP-완전 문제는 NP 안에서 가장 어려운 문제들로, 그중 하나라도 다항 시간에 풀리면 NP 전체가 풀린다. P = NP 인지는 아직 아무도 모른다.
왜 필요한가
4부 내내 “이 알고리즘은 Θ(n log n) 이다” 처럼 빠른 해법을 찾았다. 그런데 어떤 문제는 아무리 노력해도 다항 시간 알고리즘이 나오지 않는다. 배낭 문제(DP 가 의사 다항 시간이었다), 외판원 문제, 일정 짜기, 논리식 만족 가능성 같은 것들이다.
이때 “내가 못 찾은 것인가, 원래 어려운 것인가” 를 구분하는 도구가 NP-완전성이다. 어떤 문제가 NP-완전임을 보이면, 다항 시간 정확 해법을 찾는 대신 근사·휴리스틱·특수 사례·지수 알고리즘의 최적화로 방향을 바꿀 근거가 생긴다. 실무에서 시간을 아끼는 판단이다.
핵심 개념
판정 문제
복잡도 클래스는 보통 “예/아니오” 로 답하는 판정 문제로 정의한다. 최적화 문제는 문턱값을 붙여 판정 문제로 바꾼다.
- 최적화: 배낭에 넣을 수 있는 최대 가치는?
- 판정: 가치 합이 K 이상이 되게 넣을 수 있는가?
판정 버전을 풀 수 있으면 K 를 이진 탐색해 최적값도 구할 수 있으므로 어려움의 정도는 본질적으로 같다.
P 와 NP
| 클래스 | 정의 | 예 |
|---|---|---|
| P | 입력 길이 n 에 대해 다항 시간 O(n^k) 에 답을 구할 수 있다 | 정렬, 최단 경로, MST, 2-SAT |
| NP | “예” 인 경우, 다항 길이의 증거(certificate)를 다항 시간에 검증할 수 있다 | SAT, 해밀턴 경로, 부분집합 합, 그래프 3-색칠 |
NP 는 “Not Polynomial” 이 아니라 Nondeterministic Polynomial 이다. 모든 선택지를 동시에 시도할 수 있는 비결정적 기계가 다항 시간에 풀 수 있는 문제라는 뜻이고, “증거를 다항 시간에 확인할 수 있다” 와 같은 정의다.
P ⊆ NP 는 자명하다. 다항 시간에 직접 풀 수 있으면 증거 없이 풀어 보면 확인도 된다. 거꾸로 NP ⊆ P 인지, 즉 확인이 쉬우면 찾기도 쉬운가 가 P vs NP 문제다. Clay 수학연구소는 이를 7개 밀레니엄 문제 중 하나로 정하고 해결에 상금을 걸었다.
환원(reduction)
문제 A 를 문제 B 로 다항 시간에 환원한다(A ≤p B)는 것은, A 의 입력을 다항 시간에 B 의 입력으로 바꿨을 때 답이 같게 만들 수 있다는 뜻이다.
A 의 입력 x ──(다항 시간 변환 f)──→ B 의 입력 f(x)
x 의 답이 "예" ⇔ f(x) 의 답이 "예"
그러면 B 를 빨리 푸는 방법이 생기는 순간 A 도 빨리 풀린다. 즉 “B 는 A 이상으로 어렵다”.
NP-어려움과 NP-완전
- NP-어려움(NP-hard): NP 의 모든 문제가 이 문제로 다항 시간 환원된다.
- NP-완전(NP-complete): NP-어려우면서 그 자신도 NP 에 속한다.
P ⊆ NP
NP-완전 = NP ∩ NP-어려움
NP-어려움에는 NP 밖의 문제도 있다 (예: 정지 문제)
P ≠ NP 라면 P 와 NP-완전은 겹치지 않는다
P = NP 라면 P = NP = NP-완전(자명한 예외 제외)
1971년 Stephen Cook 은 논리식 만족 가능성 문제(SAT)가 NP-완전임을 증명했다(같은 시기 Leonid Levin 도 독립적으로 비슷한 결과를 얻었다). NP 의 어떤 문제든 “그 문제를 푸는 비결정적 기계의 계산 과정” 을 논리식으로 적을 수 있다는 것이 핵심이다. 이듬해 1972년 Richard Karp 는 SAT 에서 출발한 환원 사슬로 21개 조합 문제가 NP-완전임을 보였다. 이후 새 문제가 NP-완전임을 보일 때는 이미 알려진 NP-완전 문제를 그 문제로 환원하기만 하면 된다.
대표적인 NP-완전 문제
| 문제 | 판정 질문 |
|---|---|
| SAT, 3-SAT | 논리식을 참으로 만드는 변수 할당이 있는가? |
| 정점 덮개 | 크기 k 이하의 정점 집합으로 모든 간선을 덮을 수 있는가? |
| 해밀턴 사이클 | 모든 정점을 한 번씩 지나는 사이클이 있는가? |
| 외판원(판정) | 길이 L 이하로 모든 도시를 도는 경로가 있는가? |
| 부분집합 합·0/1 배낭(판정) | 합이 정확히 T 인 부분집합이 있는가? / 가치 K 이상이 가능한가? |
| 그래프 k-색칠 (k ≥ 3) | 인접한 정점이 다른 색이 되게 k 색으로 칠할 수 있는가? |
비슷해 보여도 쉬운 문제가 있다. 2-SAT, 오일러 회로(모든 간선 을 한 번씩), 2-색칠(이분 그래프 판정), 최단 경로는 P 다. 문제를 조금 바꾸면 난이도가 절벽처럼 바뀐다는 점이 이 분야의 묘미다.
NP-완전을 만났을 때
- 입력이 작은가? n 이 30 정도면 2^n ≈ 10억이라 가지치기한 완전 탐색으로 충분할 수 있다.
- 특수한 구조가 있는가? 그래프가 트리이거나 숫자가 작으면(의사 다항 DP) 효율적으로 풀린다.
- 근사로 충분한가? 정점 덮개는 최적의 2배 이내 근사가 쉽다. 거리가 삼각 부등식을 만족하는 외판원 문제는 MST 기반 2-근사가 있다.
- 실용 솔버를 쓴다. 현대 SAT 솔버와 정수 계획법(ILP) 솔버는 최악은 지수지만 실제 산업 문제의 상당수를 빠르게 푼다.
직접 해 보기
SAT 에서 “증거 확인” 과 “증거 찾기” 의 비용 차이를 본다. python3 로 실행해 확인했다.
import itertools, random
# CNF: 각 절은 리터럴 목록. 양수 i = x_i, 음수 -i = NOT x_i
def verify(cnf, assign):
"""증명서(할당)가 주어지면 다항 시간에 확인: O(전체 리터럴 수)."""
return all(any(assign[abs(l)] == (l > 0) for l in clause) for clause in cnf)
def brute_force_sat(cnf, n):
"""증명서 없이 찾기: 최악 2^n 개 할당을 다 본다."""
tried = 0
for bits in itertools.product([False, True], repeat=n):
tried += 1
assign = dict(enumerate(bits, start=1))
if verify(cnf, assign):
return assign, tried
return None, tried
cnf = [[1, -2], [2, 3], [-1, -3], [-3, 2]] # (x1∨¬x2)∧(x2∨x3)∧(¬x1∨¬x3)∧(¬x3∨x2)
print(brute_force_sat(cnf, 3))
# 해가 없는 식: x1 과 ¬x1 을 동시에 요구 + 나머지 변수는 들러리
random.seed(0)
for n in (10, 14, 18):
cnf = [[1], [-1]] + [[random.choice([1, -1]) * random.randint(2, n)] for _ in range(3)]
sol, tried = brute_force_sat(cnf, n)
print(f"n={n:2d} 만족 가능={sol is not None} 시도한 할당={tried:>7,}")
출력:
({1: True, 2: True, 3: False}, 7)
n=10 만족 가능=False 시도한 할당= 1,024
n=14 만족 가능=False 시도한 할당= 16,384
n=18 만족 가능=False 시도한 할당=262,144
verify 는 절과 리터럴을 한 번씩 훑을 뿐이라 식 크기에 선형이다. 이것이 “NP 에 속한다” 의 증거다. 반면 증거 없이 찾는 brute_force_sat 은 해가 없을 때 2^n 개 할당을 모두 확인한다. 변수가 4개 늘 때마다 16배다. 변수 60개면 2^60 ≈ 10^18 이다.
물론 이 예제의 식은 x1 과 ¬x1 이 바로 모순이라 사람 눈에는 즉시 보인다. 실제 SAT 솔버는 이런 추론(단위 전파, 충돌 학습)으로 대부분의 공간을 가지치기한다. 그래도 최악에 다항 시간을 보장하는 방법은 알려져 있지 않다.
현업에서는
- 스케줄링과 빈 패킹. 파드를 노드에 자원 낭비 없이 채우는 문제는 빈 패킹(bin packing)의 변형이고, 판정 버전이 NP-완전이다. 쿠버네티스 스케줄러가 파드 하나씩 점수를 매겨 탐욕적으로 배치하는 것도, 최적 배치를 매번 구하는 게 현실적이지 않기 때문이다. 홈랩처럼 노드가 몇 대뿐이어도 파드 조합이 늘면 수작업 최적 배치는 금방 한계에 닿는다.
- 의존성 해석. 패키지 버전 제약을 모두 만족하는 조합을 찾는 문제는 일반적으로 NP-완전으로 알려져 있다. 그래서 일부 패키지 관리자는 내부에 SAT 솔버를 쓰고, 해석이 오래 걸리거나 실패할 때 사람이 제약을 풀어 줘야 한다.
- 설정 검증과 형식 검증. 하드웨어 검증, 방화벽 규칙 충돌 검사, 프로그램 검증 도구는 문제를 SAT/SMT 로 바꿔 솔버에 넘긴다. NP-완전이라는 사실이 “포기” 가 아니라 “검증된 범용 솔버로 위임” 이라는 실용적 선택으로 이어진다.
- 면접과 설계 판단. 요구사항이 “모든 조합 중 최적” 을 요구하면 먼저 NP-어려운 문제인지 의심한다. 그렇다면 정확한 최적 대신 “충분히 좋은” 해와 시간 제한을 요구사항에 명시하는 편이 낫다.
확인 문제
- NP 가 “다항 시간에 풀 수 없는 문제” 라는 설명은 왜 틀렸는가?
- 문제 A 가 NP-완전이고 A ≤p B 이며 B 가 NP 에 속한다. B 에 대해 무엇을 말할 수 있는가?
- 0/1 배낭 DP 가 Θ(nW) 인데도 P = NP 를 증명한 것이 아닌 이유는?
- 2-SAT 은 P, 3-SAT 은 NP-완전이다. 이 사실이 주는 교훈은?
풀이
- NP 는 “증거를 다항 시간에 확인할 수 있는 문제” 이고, P 의 모든 문제도 NP 에 속한다. NP 의 모든 문제가 어렵다는 뜻이 아니며, 어떤 NP 문제가 다항 시간에 풀 수 없는지조차 증명되지 않았다(그게 P vs NP 다).
- B 도 NP-완전이다. NP 의 모든 문제가 A 로 환원되고 A 가 B 로 환원되므로(환원은 합성 가능) B 는 NP-어렵고, B 가 NP 에 속하므로 NP-완전이다.
- W 는 입력의 값이지 길이가 아니다. W 를 표현하는 비트 수 log W 에 대해 Θ(nW) 는 지수적이므로 다항 시간 알고리즘이 아니다(의사 다항 시간).
- 문제의 작은 변화(절 크기 2→3)가 난이도를 다항에서 NP-완전으로 바꿀 수 있다. 어려워 보이는 문제도 제약을 조금 바꾸면 쉬워질 수 있으니, 요구사항의 어떤 부분이 어려움을 만드는지 찾는 것이 중요하다.
더 읽을거리 (References)
- Stephen A. Cook, “The Complexity of Theorem-Proving Procedures”, Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC), 1971.
- Richard M. Karp, “Reducibility among Combinatorial Problems”, in Complexity of Computer Computations, Plenum Press, 1972.
- Clay Mathematics Institute, P vs NP
- NIST Dictionary of Algorithms and Data Structures, NP, NP-complete