패리티 P

Parity P

계산 복잡성 이론에서 복잡도 등급 ⊕P("패리티 P"로 발음됨)는 다항식 시간에 비계수적 튜링 기계가 해결할 수 있는 의사결정 문제의 등급으로, 허용 조건은 수용 경로의 수가 홀수인 것이다.⊕P 문제의 예로는 "특정 그래프에 홀수 수의 완벽한 일치가 있는가?"가 있다.클래스는 1983년 파파디미트리오와 자코스에 의해 정의되었다.[1]

⊕P는 카운팅 클래스로서, 해당 #P 문제에 대한 해답의 최하위 부분을 찾아내는 것으로 볼 수 있다.가장 중요한 비트를 찾는 문제는 PP에 있다. PP는 ⊕P보다 상당히 어려운 등급으로 여겨진다. 예를 들어 1998년 Beigel, Buhrman, Fortnow에서 보듯이 P = ⊕P ≠ NP = PP = EXPTIME이 있는 상대화된 우주(오라클 머신 참조)[2]가 있다.

토다의 정리를 보면 P가PP PH를 포함하고 있다는 것을 알 수 있지만, P는⊕P NP조차 포함하고 있지 않은 것으로 알려져 있다.그러나 토다의 정리 증명의 첫 부분은 BPP가⊕P PH를 포함하고 있다는 것을 보여준다.랜스 포트노우는 이 정리에 대한 간결한 증거를 썼다.[3]

⊕P는 그래프 이형성 문제를 포함하고 있으며, 실제로 이 문제는 ⊕P에 대해 낮다.[4]또한 UP의 모든 문제가 0 또는 하나의 허용 경로를 가지기 때문에 사소한 UP도 포함하고 있다.보다 일반적으로 ⊕P는 그 자체로 낮은데, 이는 그러한 기계가 ⊕P 문제를 즉시 해결할 수 있는 것으로부터 전력을 얻지 못한다는 것을 의미한다.

클래스 이름의 ⊕ 기호는 부울 대수에서 ⊕ 기호를 사용하여 배타적 분리 연산자를 참조하기 위한 참조일 수 있다.이는 "수락"을 1로 간주하고 "수락하지 않음"을 0으로 간주하면, 기계의 결과는 각 계산 경로의 결과를 배타적으로 분리하는 것이기 때문에 타당하다.

외부 링크

참조

  1. ^ C. H. 파파디미트리오와 S. 자코스.셈의 힘에 대한 두 가지 발언.제6차 이론 컴퓨터 과학 강의 노트 제145권, Springer-Verlag, 페이지 269–276. 1983.
  2. ^ R. 베이글, H. 부어만, L. 포트나우NP는 고유한 솔루션을 탐지하는 것만큼 쉽지 않을 수 있다.ACM STOC'98의 '절차서'에서, 페이지 203–208. 1998.
  3. ^ Fortnow, Lance (2009), "A simple proof of Toda's theorem", Theory of Computing, 5: 135–140, doi:10.4086/toc.2009.v005a007
  4. ^ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity, 2 (4): 301–330, doi:10.1007/BF01200427.