MAX-SNP
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 MAX-SNP는 최적화 문제의 근사 가능성에 대한 복잡도 종류이다. SNP는 영어: Strict NP를 줄인 말이라고 한다. strict가 붙은 것은 MAX-SNP가 NP에 대한 약한 검증자(weak verifier)와 관련되기 때문이다.
MAX-SNP 문제는 MAX-SNP0 이라는 문제로 L-환산(L-reduction)이 되는 최적화 문제의 집합이다. L-환산이란 NP-난해를 증명할 때 쓰는 다항 시간 환산과 달리 근사 가능성까지 보존하는 환산이다. 따라서 MAX-SNP는 MAX-SNP0와 근사 가능성이 같은 문제의 집합이라고 볼 수 있다. 뒤에 나오는 결과를 써서 정리하면 이것은 상수 근사가 가능한 문제의 집합과 같다.
MAX-SNP-완전도 있다. NP-완전과 비슷하게 MAX-SNP-완전 문제는 PTAS을 가지지 않을 것이라고 한다. 만약 MAX-SNP-난해 문제 중 하나라도 PTAS를 가지면 다른 모든 MAX-SNP-난해 문제가 PTAS를 가질 뿐만 아니라 P=NP까지 성립하게 된다고 한다. MAX-SNP-완전 역시 기본 문제인 MAX3SAT으로 L-환산을 해서 증명한다.
[편집] 참고문헌
- ((영어)) 복잡도 동물원 MaxSNP 우리
- 크리스토스 파파디미트리우 (1993). “13: 근사 가능성(Approximibility)”, 《Computational Complexity》 (영어). Addison Wesley, 299-328. ISBN 0-201-53082-1.