PPA(복잡성)

계산 복잡성 이론에서 PPA는 "다항식 패리티 인수"(그래프에서)를 나타내는 복잡도 등급이다.크리스토스^[1] 파파디미트리오가 1994년(528쪽)에 소개한 PPA는 TFNP의 하위 클래스다.그것은 손떨림 보조마사의 적용으로 총체적으로 보여질 수 있는 검색 문제의 한 종류다: 도수가 홀수인 정점을 가진 모든 비방향 그래프는 도수가 홀수인 다른 정점을 가지고 있어야 한다.이 관찰은 우리에게 그래프와 홀수도의 꼭지점이 주어지고, 다른 홀수도의 꼭지점을 찾도록 요구받으면, 우리는 존재한다고 보장된 것을 찾고 있다는 것을 의미한다(그러므로, 우리는 총체적인 검색 문제가 있다).

정의

PPA는 다음과 같이 정의된다.정점이 $n{\displaystyle }$ ${\displaystyle n}$ -bit$$ 이진 문자열인 그래프가 있고, 그래프는 정점을 입력으로 사용하고 인접 항목을 출력하는 다항식 크기의 회로로 표현된다고 가정합시다. (이 그래프를 사용하면 지역 탐사를 효율적으로 수행할 수 있는 기하급수적으로 큰 그래프를 나타낼 수 있다는 점에 유의하십시오.)또한 특정 꼭지점(all-zeroes 벡터라고 함)에 홀수 수의 이웃이 있다고 가정하자.우리는 또 다른 이상도 정점을 찾아야 한다.이 문제는 NP에 있다는 점에 유의하십시오. 해결책을 고려할 때 솔루션이 올바른지 회로를 사용하여 확인할 수 있다.함수 계산 문제가 이 그래프 검색 문제에 대해 다항 시간 감소를 허용하는 경우 PPA에 속한다.또한 이 그래프 검색 문제가 해당 문제로 축소될 수 있는 경우, 클래스 PPA에 대한 문제가 완료된다.

관련계급

PPAD는 지시된 그래프에 정의된 것을 제외하고 PPA와 유사한 방식으로 정의된다.PPAD는 PPA의 하위 클래스다.이는 END OF THE LINE이라고 알려진 PPAD를 정의하는 해당 문제가 (직접적으로) 추가적인 이상도 정점(본질적으로, LINE의 END에서 가장자리의 방향을 무시하는 것)을 검색하는 것으로 축소될 수 있기 때문이다.

예

• PPA를 위해 완비된 것으로 알려진 Sperner 보조정리기는 지향적이지 않은 버전이 있다.^[2]
• 합의-해결 문제는 PPA에 대해 완결된 것으로 알려져 있다.^[3]
• 3-정규 그래프에서 제2의 해밀턴 사이클을 검색하는 문제는 PPA의 멤버지만 PPA의 경우 완료되지 않은 것으로 알려져 있다.
• 정수 인자화 문제에서 PPA에 대해 완료된 문제로 무작위화된 다항식 시간 단축이 있다.^[4]

참조