NP-완전

소프트웨어 수치해석 마지막 수정: 2026-08-20 04:14:22

1. 개요[편집]

NP-완전 NP-completeness
분야	계산 복잡도 이론
정의	NP에 속하면서 NP-난해인 문제
도구	다항시간 환원 (Karp reduction)
시조	SAT (쿡-레빈 정리, 1971)
미해결	P = NP ? (밀레니엄 문제, 상금 100만 달러)

“이거 최적으로 못 풀어요”가 아니라 “이걸 빨리 풀면 저것들 전부 빨리 풀려요”가 핵심이다.

NP-완전(NP-complete)은 판정 문제 중에서 NP에 속하면서(답이 주어지면 다항시간에 검증 가능) 동시에 NP-난해(NP의 모든 문제가 이것으로 다항시간 환원됨)인 문제들을 가리킨다. 쉽게 말해 NP 안에서 가장 어려운 문제들의 무리다. 이들 중 단 하나라도 다항시간 알고리즘이 발견되면 NP 전체가 무너지며 $\mathrm{P} = \mathrm{NP}$ 가 증명되고, 반대로 하나라도 다항시간에 풀 수 없음이 증명되면 나머지 전부가 풀 수 없음이 따라온다. 수천 개의 문제가 한 배를 탄, 계산 복잡도 이론의 심장부다.¹

이 개념이 실무에서 무서운 이유는 외판원 문제, 그래프 색칠, 배낭 문제, 스케줄링, 회로 배치 등 돈이 걸린 문제 대부분이 여기 걸려 있기 때문이다. “우리 문제가 NP-완전이다”라는 말은 곧 “최악의 경우 빠른 정확해를 기대하지 말고 근사 알고리즘이나 휴리스틱으로 우회하라”는 실무적 사형 선고에 가깝다.

2. P, NP, NP-난해, NP-완전[편집]

용어가 헷갈리기로 악명 높으니 정확히 구분한다. 판정 문제(답이 예/아니오)를 기준으로 한다.

P — 다항시간에 푸는 결정론적 알고리즘이 있는 문제. “쉬운 문제”의 형식적 정의.
NP — 답이 “예”일 때 그 증거(certificate)가 주어지면 다항시간에 검증할 수 있는 문제. 비결정론적 튜링 기계로 다항시간에 푸는 문제라고 정의해도 같다. NP는 “빨리 검증”이지 “빨리 풀기”가 아니다 — 이 오해가 제일 흔하다.
NP-난해(NP-hard) — NP의 모든 문제가 이것으로 다항시간 환원되는 문제. 난이도의 하한만 규정하므로, 판정 문제가 아니어도(최적화·함수 문제) 되고 NP에 속하지 않아도(더 어려워도) 된다.
NP-완전(NP-complete) — NP-난해이면서 동시에 NP에 속하는 문제. 즉 $\text{NP-완전} = \text{NP} \cap \text{NP-난해}$ .

$\mathrm{P} \subseteq \mathrm{NP}$ 는 자명하다(풀 수 있으면 검증도 된다). 문제는 그 역, 즉 $\mathrm{P} = \mathrm{NP}$ 인지 여부다. 대부분의 이론가는 $\mathrm{P} \ne \mathrm{NP}$ 라고 믿지만 아무도 증명하지 못했고, 이것이 계산 복잡도의 최대 미해결 문제이자 밀레니엄 문제 중 하나다.

3. 다항시간 환원 (Karp 환원)[편집]

NP-완전 이론 전체를 떠받치는 도구가 다항시간 다대일 환원(polynomial-time many-one reduction), 흔히 Karp 환원이다. 문제 $A$ 를 문제 $B$ 로 환원한다는 것( $A \le_p B$ )은, 임의의 $A$ 의 입력 $x$ 를 다항시간에 계산되는 함수 $f$ 로 변환해

x \in A \iff f(x) \in B

가 성립하게 만드는 것이다. 직관은 “ $B$ 를 풀 수 있으면 $A$ 도 풀 수 있다”이므로 $B$ 는 $A$ 만큼은 어렵다. 이 관계가 이행적( $A \le_p B$ 이고 $B \le_p C$ 면 $A \le_p C$ )이라는 점이 결정적이다.

여기서 NP-완전성을 도미노처럼 퍼뜨리는 핵심 정리가 나온다.

$B$ 가 NP-완전이고, $B \le_p A$ 이며, $A \in \mathrm{NP}$ 이면, $A$ 도 NP-완전이다.

즉 이미 알려진 NP-완전 문제 하나를 새 문제로 환원하기만 하면 새 문제의 NP-완전성이 증명된다. 그래서 실전 증명은 언제나 “ $A$ 가 NP에 속함을 보이고(검증자 제시), 알려진 NP-완전 문제 $B$ 를 $A$ 로 환원한다” 두 단계다. 환원 방향을 거꾸로 잡는 것( $A \le_p B$ )이 초심자의 국룰 실수 — 그건 $A$ 가 쉽다는 얘기라 아무것도 증명하지 못한다.²

4. 쿡-레빈 정리 — 최초의 NP-완전 문제[편집]

그런데 이 도미노를 쓰려면 맨 처음 쓰러뜨릴 도미노, 즉 아무 사전 지식 없이 NP-완전임을 직접 증명한 문제가 하나는 있어야 한다. 그게 쿡-레빈 정리(Cook–Levin theorem, 1971년 스티븐 쿡, 그리고 독립적으로 레오니트 레빈)다.

불리 충족가능성 문제(SAT)는 NP-완전이다.

SAT은 불리 변수들의 논리식(예: $(x_1 \lor \lnot x_2) \land (x_2 \lor x_3)$ )이 참이 되게 하는 변수 대입이 존재하는지를 묻는다. 증명의 핵심은 NP의 임의 문제를 푸는 비결정론적 튜링 기계의 계산 과정 전체를, 테이프 셀·상태·시간 스텝을 변수로 삼는 거대한(그러나 다항 크기의) 불리 논리식으로 인코딩해서, “그 기계가 받아들이는 실행이 존재한다 ⟺ 그 논리식이 충족가능하다”를 만드는 것이다. 계산 그 자체를 논리식으로 번역한 셈이라, 이후 모든 NP-완전 증명의 뿌리가 된다.

5. 환원 사슬과 대표 완전 문제[편집]

쿡-레빈으로 SAT이 완전임이 서면, 나머지는 SAT에서 뻗어 나가는 환원 사슬로 정복된다. 1972년 리처드 카프가 21개 문제의 NP-완전성을 한 논문에서 보이며 판을 정리했다. 대표적인 사슬:

\text{SAT} \le_p \text{3-SAT} \le_p \text{CLIQUE} \le_p \text{정점 덮개} \le_p \cdots

3-SAT — 각 절(clause)이 리터럴 3개인 SAT. SAT에서 긴 절을 쪼개는 표준 환원으로 완전성이 옮겨간다. 대부분의 후속 환원이 여기서 출발한다.
최대 클리크(CLIQUE) — 그래프에서 서로 다 연결된 정점 $k$ 개가 있는가. 3-SAT의 각 절을 정점 묶음으로, 모순 없는 리터럴 사이만 간선으로 잇는 우아한 환원.
최소 정점 덮개(Vertex Cover) — 클리크의 여그래프에서 독립집합·정점 덮개가 상보적이라는 사실로 즉시 환원.
부분합 문제(Subset Sum) — 정수 집합에서 합이 목표값이 되는 부분집합이 있는가. 3-SAT에서 자릿수 인코딩으로 환원. 배낭 문제의 판정판이 여기 포함된다.
해밀턴 순환 / TSP — 모든 정점을 한 번씩 도는 순환. 외판원 문제의 판정판이 카프의 목록에 들어 있다.
그래프 색칠(3-Coloring) — 인접 정점이 다른 색이 되도록 3색으로 칠하기. 주파수 할당·레지스터 할당의 추상형.

이 문제들이 전부 “같은 난이도”라는 것이 요점이다. 하나를 다항시간에 풀면 환원을 타고 전부 풀린다.

6. NP-난해와 구별할 것들[편집]

정지 문제 — 정지 문제는 NP-난해지만 NP-완전이 아니다. 애초에 결정 불가능(undecidable)이라 어떤 알고리즘으로도 못 풀고, NP에 속하지도 않는다. NP-난해가 “NP 상한”을 뜻하지 않는다는 산 증거.
NP-중간(NP-intermediate) — $\mathrm{P} \ne \mathrm{NP}$ 라면 P도 아니고 NP-완전도 아닌 어중간한 문제가 반드시 존재한다(래드너 정리). 소인수분해와 그래프 동형사상이 대표적 후보로, 아직 어느 쪽으로도 분류되지 않았다. 현대 암호학이 소인수분해의 어려움에 기대고 있다는 점에서 실용적으로도 중요하다.
최적화 vs 판정 — 엄밀히 NP-완전은 판정 문제의 개념이다. “최단 순회를 찾아라”는 함수 문제라 NP-난해라고 부르는 게 정확하다. 다만 판정판(“길이 $\le k$ 인 순회가 있나”)과 최적화판은 이분 탐색으로 서로 다항시간 환원되므로 실무에선 뭉뚱그린다.

7. 수치·시뮬레이션 맥락에서[편집]

NP-완전은 순수 이론처럼 보이지만 시뮬레이션·공학 파이프라인의 발목을 상시로 잡는다.

메시 분할 — 대규모 유한요소법 병렬 해석에서 통신 최소 균형 그래프 분할은 NP-난해다. 그래서 METIS 같은 도구가 정확해 대신 다단계 휴리스틱을 쓴다.
이산 설계변수 — 판재 두께·볼트 개수·부재 유무 같은 최적설계 변수는 카탈로그에서 골라야 하는 이산량이라, 연속 최적화의 매끄러움이 사라지고 조합 폭발이 온다.
경로 계획·스케줄링 — 로봇 작업 순서, 경로 계획, 생산 스케줄이 TSP·색칠·집합덮개 변형으로 귀결된다.

이 모든 경우의 실무 처방은 동일하다 — 최악 복잡도가 지수적이라는 사실과, 구조가 있는 실제 인스턴스가 잘 풀린다는 사실은 공존한다. 분지한정법, LP 완화 기반 정수계획법 솔버, 그리고 성능 보증이 붙은 근사 알고리즘으로 우회하는 것이 정석이다. 자세한 알고리즘 스펙트럼은 조합 최적화 문서에 정리돼 있다.³

8. 관련 문서[편집]

인기 자료로 개럿·존슨(Garey & Johnson)의 Computers and Intractability(1979)가 있는데, 부록의 NP-완전 문제 목록만 100쪽이 넘는다. 표지의 그림 — 상사에게 “이 문제 못 풀겠는데요”라고 변명하는 세 컷 만화 — 은 이 바닥 최고의 밈이다. “못 풀겠습니다”보다 “저뿐 아니라 아무도 못 풉니다”가 훨씬 안전한 보고라는 교훈. ↩
환원 방향은 “어려운 걸 새 문제에 심는다”로 외우면 된다. 알려진 어려운 문제 $B$ 를 내 문제 $A$ 안에 인코딩해서, $A$ 를 풀면 $B$ 도 풀리게 만드는 것. 반대로 하면 “내 문제가 쉬운 문제로 환원된다”가 되어 완전성 증명이 아니라 알고리즘 설계가 돼버린다. ↩
$\mathrm{P} \ne \mathrm{NP}$ 를 증명했다는 논문은 매년 수십 편씩 arXiv에 올라오고 대부분 틀렸다. 게재를 워낙 많이 시도해서 게러드 우친(Gerhard Woeginger)이 “P-versus-NP page”에 116편(2016년 기준)을 아카이빙해 뒀을 정도. 증명했다는 확신이 들면, 먼저 어디가 틀렸는지 찾는 게 정신 건강에 이롭다. ↩