1. 다시, 답을 ‘검증’한다는 것
주어진 부울 식 ϕ에 대해 “ϕ는 만족 가능한가?”를 물으면 직관적으로 어렵다. 변수 n개라면 2n가지 대입을 다 시험해 보는 게 가장 단순한 방법이고, 더 영리한 방법이 있는지는 — 솔직히 말해 — 아무도 모른다. 그러나 누군가가 “이 변수 대입이 ϕ를 만족시킨다”고 알려준다면 우리는 그 주장을 빠르게 확인할 수 있다. ϕ에 대입을 꽂고 평가하면 끝이다.
이 비대칭이 NP의 본질이다. NP는 답을 찾는 클래스가 아니라 답을 검증하는 클래스다.
비유하자면 P는 “스스로 수학 문제를 푸는 학생”, NP는 “해답지를 받았을 때 그것이 옳은지 빠르게 채점하는 조교”의 클래스다. 풀이가 어렵다고 채점까지 어려우란 법은 없다.
2. NP의 두 정의
NP는 두 가지 방식으로 정의된다. 다행히 둘은 동치다.
정의 14.1 (비결정적 시간). 비결정적 TM(NTM)이 모든 길이 n 입력에 대해 어떤 계산 분기에서든 t(n)단계 안에 멈춘다면, 그 NTM의 실행 시간은 t(n)이다. 클래스 NTIME(t(n))은 어떤 NTM이 O(t(n)) 시간에 결정하는 언어들의 모임이다.
NP1 = ⋃k ≥ 1 NTIME(nk).
정의 14.2 (인증서·검증기). 언어 A가 NP2에 속한다는 것은, 다음을 만족하는 결정적 다항 시간 TM V(검증기, verifier)가 존재한다는 것이다:
w ∈ A ⟺ 어떤 c, |c| ≤ p(|w|), V는 ⟨w, c⟩를 수락한다.
여기서 c는 인증서(certificate) 또는 증명서다.
정리 14.3. NP1 = NP2.
증명 스케치. (⊇) V가 다항 시간 검증기라면, NTM N은 입력 w에 대해 길이 ≤ p(|w|)의 인증서 c를 비결정적으로 추측한 뒤 V(w, c)를 시뮬레이션한다. V가 수락하면 N도 수락. 각 분기는 다항 시간이므로 N은 NP1 안에 있다.
(⊆) NTM N이 w를 수락한다면, 수락 분기를 따라 내려가는 비결정 선택의 수열이 존재한다. 그 수열을 인증서 c로 삼는다. 검증기 V는 ⟨w, c⟩를 받아 c가 지시하는 선택대로 N을 시뮬레이션하고 수락 여부를 따라간다. 분기가 다항 깊이이므로 인증서도 다항 길이, 검증도 다항 시간이다. ∎
이후로 그냥 NP라고 부른다. 핵심은 표어처럼 적힌다. NP = 다항 길이의 증명서가 존재하면 다항 시간에 검증할 수 있는 문제들.
3. NP 거주민들 — 인증서를 보면 안다
다음 문제들이 NP에 속함을 일일이 인증서로 확인하자. 각 인증서는 직관적이다.
SAT. 부울 식 ϕ가 어떤 변수 대입에 의해 참이 되는가? 인증서는 만족시키는 변수 대입 자체. 검증은 ϕ에 대입을 꽂고 평가 — 다항 시간.
3SAT. SAT의 특수 형태로, ϕ가 절(clause)당 정확히 3개의 리터럴을 가지는 CNF 형태. 인증서·검증은 SAT와 같다.
CLIQUE. ⟨G, k⟩에 대해 G에 크기 k의 완전 부분 그래프가 있는가? 인증서는 그 k개의 정점 집합. 검증은 모든 쌍이 간선인지 확인 — O(k2) 시간.
INDEPENDENT-SET. ⟨G, k⟩에 대해 서로 인접하지 않은 k개의 정점이 있는가? 인증서는 그 정점 집합. 검증은 어떤 쌍도 간선이 아닌지 확인.
VERTEX-COVER. ⟨G, k⟩에 대해 모든 간선의 양 끝 중 적어도 하나를 덮는 k개의 정점이 있는가? 인증서는 그 정점 집합.
HAMPATH. ⟨G, s, t⟩에서 s를 출발해 모든 정점을 정확히 한 번씩 방문하고 t에서 끝나는 경로가 있는가? 인증서는 그 정점 순서.
SUBSET-SUM. ⟨{x1, …, xn}, t⟩에 대해 부분 집합의 합이 정확히 t인가? 인증서는 그 부분 집합.
일곱 문제 모두 검증은 누가 봐도 다항 시간이다. 그러나 답을 찾는 다항 알고리즘은 — 50년 동안 — 아무도 발견하지 못했다.
4. P ⊆ NP, 그리고 천만 달러
P에 속하는 언어 A에 대해, 검증기 V는 인증서를 무시하고 그냥 결정 알고리즘을 돌리면 된다. 즉 P ⊆ NP는 자명하다.
정리 14.4. P ⊆ NP.
그렇다면 반대 방향, NP ⊆ P? 풀어 쓰면 “답을 빠르게 검증할 수 있다면 답도 빠르게 찾을 수 있는가?” 이것이 P 대 NP 문제이고, 클레이 수학 연구소의 밀레니엄 문제 일곱 중 하나로 백만 달러가 걸려 있다. 대다수 컴퓨터 과학자는 P ≠ NP를 믿는다. 그 이유는 이론적이라기보다 경험적이다 — 수십 년간 수만 명이 NP의 자연 문제 수천 개에 다항 알고리즘을 못 찾았으니까.
만약 P = NP가 증명된다면, 현대 암호 체계의 절반 이상이 일주일 안에 무너진다. 이론가들이 이 등식의 진실성을 의심하는 데에는 “세상이 저렇게 친절할 리 없다”는 생활 감각도 한몫한다.
5. 다항 시간 매핑 환원
NP 안에서 어떤 문제가 다른 문제보다 “적어도 같은 만큼 어렵다”는 것을 어떻게 표현하나? 답은 환원(reduction)이다. 결정 가능성의 환원은 사상 환원(mapping reduction)이었는데, 여기서는 그 환원이 다항 시간 안에 계산되어야 한다.
정의 14.5 (다항 시간 매핑 환원). 언어 A에서 B로의 다항 시간 매핑 환원(polynomial-time mapping reduction)이란 다항 시간에 계산되는 함수 f: Σ* → Σ*가 존재하여 모든 w에 대해
w ∈ A ⟺ f(w) ∈ B
이 성립하는 것을 말한다. 이때 A ≤p B라 쓴다.
정리 14.6. A ≤p B 이고 B ∈ P 이면 A ∈ P.
f가 A에서 B로의 다항 시간 환원이고 M이 B의 다항 시간 결정기라 하자. A의 결정기 M′은 입력 w에 대해 f(w)를 계산한 뒤 M(f(w))를 돌려 그 결과를 출력한다. f의 계산 시간이 다항이므로 |f(w)| 또한 입력 길이의 다항이다. M의 시간은 |f(w)|의 다항이므로 합성한 M′의 시간도 |w|의 다항이다. 즉 A ∈ P. ∎
대우를 취하면 더 유용한 형태가 된다. A ≤p B 이고 A ∉ P 이면 B ∉ P. 즉 환원은 어려움을 “옮긴다” — 쉬운 문제로 줄어드는 어려운 문제는 사실 어렵지 않았다는 모순이 생기므로, 어려움이 환원의 목표 쪽으로 흘러간다.
같은 논리는 NP에도 적용된다 — A ≤p B이고 B ∈ NP이면 A ∈ NP. 환원은 P, NP 모두를 보존한다.
6. 환원 실전: 3SAT ≤p CLIQUE
이론은 충분하니 사례 하나를 구체적으로. 3SAT 인스턴스를 CLIQUE 인스턴스로 다항 시간 안에 변환할 수 있고, 변환 결과의 답이 곧 원본의 답이 되는 사상을 만들겠다.
정리 14.7. 3SAT ≤p CLIQUE.
입력은 k개의 절을 가진 3CNF 식 ϕ = (a1 ∨ b1 ∨ c1) ∧ … ∧ (ak ∨ bk ∨ ck). 각 ai, bi, ci는 리터럴(변수 또는 그 부정)이다.
변환 함수 f가 출력하는 그래프 G와 정수 k는 다음과 같다. 그래프의 정점은 ϕ의 모든 리터럴 자리(literal occurrence) 하나당 한 개씩 — 따라서 정확히 3k개. 정점들은 각 절에 해당하는 그룹(triple)으로 묶인다. 같은 그룹 안의 정점끼리는 간선을 두지 않는다. 다른 그룹의 두 정점 사이에는, 두 리터럴이 서로의 부정이 아니라면 간선을 둔다(즉 모순되지 않는 한 연결).
이제 ϕ가 만족 가능 ⟺ G에 크기 k의 클리크가 있음을 보인다.
(⇒) ϕ가 만족 가능하면 만족시키는 대입이 있다. 각 절은 적어도 하나의 참 리터럴을 가지므로, 절마다 참 리터럴 하나씩을 골라 그 정점 k개를 모은다. 같은 변수의 모순된 리터럴(예: x와 ¬x)이 동시에 참일 수는 없으므로 이 k개 정점 사이에는 모두 간선이 있다. 따라서 k-클리크.
(⇐) G에 크기 k의 클리크가 있다고 하자. 같은 그룹 안에는 간선이 없으므로 클리크의 k개 정점은 서로 다른 절에서 하나씩 나와야 한다. 또 클리크 안의 두 리터럴은 모순되지 않으므로 일관된 변수 대입이 가능하다 — 클리크에 등장하는 리터럴을 모두 참으로 두고, 나머지 변수는 임의로 둔다. 각 절에서 클리크에 속한 리터럴이 참이 되었으므로 ϕ가 만족된다.
f의 계산 시간은 정점 3k개와 그래프 간선 O(k2)개를 적는 것뿐이라 다항이다. 결론. ∎
이 환원의 매력은 단순함이다 — 절 → 그룹, 모순 없음 → 간선, 만족 가능성 → 클리크. 어려움이 옷만 갈아입었을 뿐 사라지지 않았다는 사실을, 그래프라는 옷에 비추어 다시 본 셈이다.
그렇다면 자연스러운 질문. 어떤 NP 문제든 SAT로 환원할 수 있는가? 그리고 SAT에서 출발해 다른 모든 NP 문제로도 환원할 수 있는가? 이 질문의 답이 “그렇다”라면, 단 하나의 문제만 P에 들어가도 NP 전체가 P에 빨려 들어간다. 이 경계선상의 문제들이 NP-완전이고, 다음 강의의 주인공이다.