MAX-SNP

계산 복잡도 이론에서 MAX-SNP는 최적화 문제의 근사 가능성에 대한 복잡도 종류이다. SNP는 Strict NP를 줄인 말이다. 엄격한(strict)이라는 말이 앞에 붙은 이유는 MAX-SNP가 NP에 대한 약한 검증자(weak verifier)와 관련되기 때문이다.

MAX-SNP 문제는 MAX-SNP₀이라는 문제로 L-환산(L-reduction)이 되는 최적화 문제의 집합이다. L-환산이란 NP-난해를 증명할 때 쓰는 다항 시간 환산과 달리 근사 가능성까지 보존하는 환산이다. 따라서 MAX-SNP는 MAX-SNP₀과 근사 가능성이 같은 문제의 집합이라고 볼 수 있다. 뒤에 나오는 결과를 써서 정리하면 이것은 최적해의 상수배 이내로 근사가 가능한 문제의 집합과 같다.

다른 복잡도 종류와 비슷하게 MAX-SNP-완전과 MAX-SNP-난해 복잡도 종류도 정의할 수 있다. NP-완전이 다항 시간에 풀리지 않을 것으로 예상되는 문제의 집합인 것과 비슷하게, MAX-SNP-완전 문제는 PTAS를 가지지 않을 것으로 예상되는 문제의 집합이다. 만약 MAX-SNP-난해 문제 중 하나라도 PTAS를 가지면 다른 모든 MAX-SNP-난해 문제가 PTAS를 가질 뿐만 아니라 P=NP까지 성립하게 된다. 현재 학계에서는 P와 NP는 다르다고 보고 있으므로, MAX-SNP-난해 문제 역시 PTAS를 가지지 않을 것으로 본다. 어떤 문제가 MAX-SNP-완전인지 아닌지는 주로 기본 문제인 MAX3SAT으로 L-환산을 해서 증명한다. 이는 NP-완전을 증명할 때 충족 가능성 문제로 다항 시간 환산을 하는 것과 비슷하다.

참고 문헌

• (영어) 복잡도 동물원 MaxSNP 우리
• 크리스토스 파파디미트리우 (1993). 〈13: 근사 가능성(Approximibility)〉. 《Computational Complexity》 (영어). Addison Wesley. 299-328쪽. ISBN 0-201-53082-1.