SNP(복잡성)

SNP (complexity)

계산 복잡성 이론에서 SNP(Strict NP로부터)는 그래프 이론적 속성의 관점에서 논리적 특성화에 기초한 NP의 제한된 부분집합을 포함하는 복잡성 등급이다.그것은 최적화 문제의 클래스 MaxSNP의 정의의 기초를 형성한다.

이는 다음과 같은 형식의 2차 논리 공식으로 표현 가능한 관계 구조(그래프 등)의 속성인 문제의 등급으로 정의된다.

,

where are relations of the structure (such as the adjacency relation, for a graph), are unknown relations (sets of tuples of vertices), and is a quantifier-free formula: any boolean co관계의 [1]축소즉, 실존적 2차 계량화(관계 상공)만 허용되고 보편적 1차 계량화(정점 이상)만 허용된다.정점에 대한 실존적 정량화도 허용된다면, 결과적 복잡도 등급은 파긴의 정리라고 알려진 사실인 NP(더 정확히 말하면 NP에 있는 관계 구조의 그러한 속성 등급)와 같을 것이다.

예를 들어 SNP는 다음과 같은 공식으로 표현될 수 있기 때문에 3-색상(특정 그래프의 색상이 3인지 여부를 결정하는 문제)을 포함한다.

.

여기서 은 입력 그래프의 인접 관계를 나타내며, 세트(단일 관계) ,S , 3 는 3가지 색상 중 하나로 색칠된 정점 집합에 해당한다.마찬가지로 SNP는 k-SAT 문제, 즉 공식이 결합 정상 형태와 k가 고정된 조항당 최대 kL로 제한되는 부울 만족도 문제(SAT)를 포함한다.

맥스SNP

유사한 정의는 모든 튜플에 대해 공식을 만족하도록 요구하는 대신, 공식이 만족하는 튜플의 수를 최대화하고자 할 때 최적화 문제를 고려한다.즉, MaxSNP는0 다음과 같은 형태로 표현 가능한 관계 구조물에 대한 최적화 문제의 등급으로 정의된다.

그런 다음 MaxSNP는 MaxSNP의0 문제에 대한 L 축소(로그 공간 축소가 아닌 선형 축소)와 관련된 모든 문제의 등급으로 정의된다.[2]예를 들어, MAX-3SAT는 MaxSNP의0 문제: 3-CNF-SAT의 인스턴스(instance of the 3-CNF-SAT, containment norm formative and important in cloon)를 주어진 경우, 가능한 한 많은 조항을 만족하는 과제를 찾는다.사실, 그것은 맥스NP에게 자연스러운 완전한 문제다.

MaxSNP의 모든 문제를 해결하기 위한 고정 비율 근사 알고리즘이 있기 때문에 MaxSNP는 일정 비율 내에 근접한 모든 문제의 등급인 APX에 포함되어 있다.사실 PTAS 감소에 따른 MaxSNP의 폐쇄(L-축소보다 약간 더 일반적임)는 APX와 같다. 즉, APX의 모든 문제는 MaxSNP의 어떤 문제로부터 PTAS 감소를 받는다.특히 모든 MaxSNP-완전성 문제(L-축소 또는 AP-축소)는 APX-완전성(PTAS축소)이므로 P=NP가 아니면 PTAS를 인정하지 않는다.그러나, 이에 대한 증명은 PCP 정리에 의존하는 반면, MaxSNP-완전성의 증명은 종종 초보적인 경우가 많다.

참고 항목

참조

  1. ^ Feder, Tomás; Vardi, Moshe Y. (1993). "Monotone monadic SNP and constraint satisfaction". Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. doi:10.1145/167088.167245.
  2. ^ Papadimitriou, Christos H.; Yannakakis, Mihalis (1991). "Optimization, approximation, and complexity classes". J. Comput. Syst. Sci. 43 (3): 425–440. Zbl 0765.68036.

외부 링크