NP-완전성: 어려운 문제의 경계

지난 글로 계산기하 파트를 마쳤습니다. 이번 글에서는 계산 복잡도 이론(computational complexity theory)을 다룹니다. 지금까지 우리는 “이 문제를 어떻게 빨리 풀까”를 고민했습니다. 하지만 어떤 문제들은 수십 년간 누구도 빠른 알고리즘을 찾지 못했습니다. 그렇다면 질문을 바꿔야 합니다. “이 문제는 정말로 본질적으로 어려운가?” 이 질문에 답하는 틀이 바로 NP-완전성입니다.

결정 문제와 다항 시간

복잡도 이론은 보통 결정 문제(decision problem), 즉 답이 “예/아니오”인 문제를 다룹니다. “이 그래프에 크기 k인 클릭이 있는가?”처럼요. 최적화 문제도 임곗값을 붙이면 결정 문제로 바꿀 수 있습니다.

핵심 기준은 다항 시간(polynomial time)입니다. 입력 크기 n에 대해 O(n^c) 안에 끝나면 “효율적”으로 간주합니다. 지수 시간 O(2ⁿ)은 n이 조금만 커져도 실용 불가능합니다. 이 다항 vs 지수의 경계가 이론 전체의 기준선입니다.

P와 NP

두 가지 핵심 클래스를 정의합니다.

P: 다항 시간에 풀 수 있는 결정 문제들. 정렬, 최단 경로, 최대 유량 등.
NP: 답이 “예”일 때, 그것을 뒷받침하는 증명서(certificate)가 주어지면 다항 시간에 검증할 수 있는 문제들.

P, NP, NP-완전, NP-난해

NP의 N은 흔한 오해와 달리 “non-polynomial”이 아니라 nondeterministic(비결정적)의 약자입니다. 비결정적 튜링 기계가 다항 시간에 푼다는 정의와, 다항 시간에 검증 가능하다는 정의는 동치입니다.

P에 속한 문제는 당연히 NP에도 속합니다(풀 수 있으면 검증도 할 수 있으니까). 그래서 P ⊆ NP입니다. 반대로 P = NP인가, 즉 검증이 빠른 모든 문제는 푸는 것도 빠른가는 컴퓨터 과학 최대의 미해결 문제입니다.

찾기는 어려워도 검증은 쉽다

NP의 직관을 가장 잘 보여주는 예가 SAT(논리식 충족 가능성)입니다. 부울 변수들의 논리식이 주어졌을 때, 식을 참으로 만드는 변수 값 배정이 존재하는지 묻습니다.

검증기와 증명서

찾기: n개 변수의 가능한 배정은 2ⁿ 가지입니다. 전부 시도하면 지수 시간이고, 더 빠른 방법은 아무도 모릅니다.
검증: 누군가 “x=참, y=참, z=참”이라는 답을 주면, 그 값을 대입해 식이 참인지 확인하는 것은 순식간입니다.

이 비대칭 — 답을 찾기는 어려운데 답이 맞는지 확인은 쉽다 — 이 NP의 본질입니다. 스도쿠를 푸는 것은 어렵지만, 채워진 답이 맞는지 보는 것은 쉬운 것과 같습니다.

NP = "예" 답에 대해
     ① 다항 크기의 증명서가 존재하고
     ② 그 증명서를 다항 시간에 검증할 수 있는 문제

NP-완전과 NP-난해

NP 안에는 특별한 위치를 차지하는 문제들이 있습니다.

NP-난해(NP-hard): NP의 모든 문제를 다항 시간에 이 문제로 환원할 수 있을 만큼 어려운 문제. NP에 속하지 않아도 됩니다.
NP-완전(NP-complete): NP에 속하면서 동시에 NP-난해인 문제. 즉 NP 안에서 가장 어려운 문제들입니다.

NP-완전 문제의 결정적 성질은 이것입니다. NP-완전 문제 중 단 하나라도 다항 시간 알고리즘이 발견되면, NP의 모든 문제가 다항 시간에 풀려 P = NP가 된다. 반대로 P ≠ NP라면 NP-완전 문제는 절대 다항 시간에 풀 수 없습니다. 그래서 어떤 문제가 NP-완전임을 보이는 것은 사실상 “효율적 알고리즘을 찾으려 애쓰지 말라”는 강력한 신호입니다.

쿡–레빈 정리: 최초의 NP-완전 문제

“모든 NP 문제를 이 문제로 환원할 수 있다”는 조건은 까다로워 보입니다. 첫 NP-완전 문제는 어떻게 찾았을까요? 쿡–레빈 정리(Cook–Levin theorem)가 SAT가 NP-완전임을 직접 증명했습니다. 임의의 NP 문제를 푸는 비결정적 튜링 기계의 계산 과정을, 그 과정이 올바른지를 나타내는 거대한 부울 논리식으로 변환할 수 있다는 것이 핵심입니다. 그 식이 충족 가능하면 원래 문제의 답이 “예”가 됩니다.

그다음은 환원의 연쇄

SAT라는 첫 NP-완전 문제가 확보되자, 이후의 증명은 훨씬 쉬워졌습니다. 새 문제 X가 NP-완전임을 보이려면 두 가지만 하면 됩니다.

X가 NP에 속함을 보인다(증명서를 다항 시간에 검증).
이미 알려진 NP-완전 문제(예: SAT, 3-SAT)를 X로 다항 시간에 환원한다.

이렇게 SAT → 3-SAT → 클릭 → 정점 덮개 → 해밀턴 경로 → TSP … 로 NP-완전성이 도미노처럼 번졌고, 오늘날 수천 개의 문제가 NP-완전으로 알려져 있습니다.

대표 NP-완전 문제	묻는 것
SAT / 3-SAT	논리식을 참으로 만드는 배정 존재?
클릭(Clique)	크기 k 완전 부분 그래프 존재?
정점 덮개	크기 k로 모든 간선을 덮나?
해밀턴 순환	모든 정점을 한 번씩 도는 순환?
부분집합 합	합이 정확히 T인 부분집합?
배낭(결정형)	가치 ≥ V를 무게 ≤ W로?

어렵다고 포기하는 건 아니다

문제가 NP-완전이라고 손을 놓아야 하는 것은 아닙니다. 실무에서는 여러 우회로가 있습니다.

근사 알고리즘: 최적해 대신 보장된 비율의 근사해를 다항 시간에.
휴리스틱·메타휴리스틱: 유전 알고리즘, 담금질 등 실용적 해법.
고정 매개변수 알고리즘: 특정 매개변수가 작을 때 효율적으로.
특수 케이스: 입력이 트리·평면 그래프 등 제한적이면 다항 시간.

NP-완전성은 “효율적 해법이 없을 가능성이 매우 크다”는 진단이지, 문제를 다루는 모든 방법을 닫는 사형 선고는 아닙니다.

다음 글에서는 P와 NP를 넘어 더 넓은 복잡도 클래스들의 지도 — PSPACE, EXPTIME, co-NP 등 — 를 그려보겠습니다.

지난 글: 다각형의 넓이: 신발끈 공식과 픽의 정리

다음 글: 복잡도 클래스: P, NP, PSPACE의 지도

읽어주셔서 감사합니다. 😊