NP 완전성: 빠른 검증과 빠른 풀이 사이의 질문
NP 완전성은 여러 결정 문제의 계산 난도를 연결하는 개념이다. 어렵다는 일상적 인상이나 알고리즘을 아직 찾지 못했다는 사실만으로 NP 완전하다고 부를 수 없다. 문제의 검증 구조와 다항시간 환원에 대한 두 조건을 증명해야 한다.
NP 완전성은 NP 소속과 모든 NP 문제의 다항 환원을 함께 요구한다. P와 NP가 같은지는 아직 해결되지 않았다.
P와 NP의 정의
P는 결정적 계산 모델에서 입력 길이에 대해 다항시간으로 판정할 수 있는 결정 문제의 집합이다. NP는 예 입력에 대해 다항 길이의 증거가 존재하고 그 증거를 다항시간에 검증할 수 있는 문제의 집합이다. 모든 P 문제는 NP에 포함된다.
SAT에서 변수 대입을 증거로 받으면 각 절이나 논리식을 평가하여 만족하는지 검사할 수 있다. 대입을 찾는 과정과 주어진 대입을 확인하는 과정은 다르다. NP의 N은 non-deterministic에서 왔으며 non-polynomial의 약자가 아니다.
SAT input: a Boolean formula F
Certificate: one truth assignment for all variables
Verifier:
evaluate F under the assignment
return YES exactly when F is true
A certificate can be checked efficiently.
That does not by itself provide an efficient way to find one.
NP는 예라고 주장하는 증거를 빠르게 검사할 수 있다는 정의다. 아니오라는 증거도 언제나 같은 방식으로 존재한다는 뜻은 아니며, 이에 관련된 co-NP는 별도 개념이다.
어려움을 모으는 두 조건
NP-hard는 모든 NP 문제가 그 문제로 다항시간 환원된다는 뜻이다. NP-complete는 NP-hard이면서 동시에 NP에 속하는 문제다. NP-hard에는 NP 밖의 문제나 최적화 형태도 포함될 수 있으므로 두 표현을 섞어 쓰면 안 된다.
새 결정 문제 B의 NP 완전성을 보이려면 우선 증거를 다항시간에 검사할 수 있음을 보인다. 그다음 이미 NP 완전한 A를 골라 A≤ₚB를 구성한다. 알려진 어려운 문제를 새 문제로 옮기는 방향이어야 한다.
Cook–Levin 정리는 SAT가 NP 완전함을 보여 이런 환원 사슬의 출발점을 제공한다. 이후 3-SAT, 클릭, 정점 커버 등 많은 문제가 연결된다. 그중 하나의 NP 완전 문제에 다항시간 알고리즘이 생기면 모든 NP 문제도 다항시간에 풀려 P=NP가 된다.
현재 P=NP 여부는 해결되지 않았다. 따라서 NP 완전이라는 사실이 다항시간 알고리즘의 불가능성을 이미 증명했다는 뜻은 아니다. 모든 현실 입력이 느리다는 뜻도 아니다. 작은 크기, 특별한 구조, 평균 사례, 근사·휴리스틱은 실제 해결에 도움이 될 수 있다.
입력의 숫자 크기에 비례하는 의사다항 알고리즘이나 특정 매개변수에 민감한 알고리즘도 정의상 다항시간과 다를 수 있다. 최적화 문제를 논의할 때는 “값이 K 이상인가” 같은 결정 형태를 명시해야 한다. 정확한 모델과 입력 길이가 난도 주장의 기준이다.