PPAD(복잡성)

PPAD (complexity)

컴퓨터 과학에서 PPAD(Polynomial Parity Crisons on Directed graphs)는 Christos Papadimitriou가 1994년에 도입한 복잡도 등급이다.PPAD는 패리티 인수로 총합으로 나타낼 수 있는 기능을 기반으로 한 TFNP의 하위 클래스다.[1][2]이 수업은 나시 평형 계산 문제를 포함하고 있기 때문에 알고리즘 게임 이론 분야에서 상당한 관심을 끌었다: 이 문제는 다스카라키스, 골드버그, 파파디미트리오가 PPAD를 위해 최소 3명의 플레이어로 완결된 것으로 나타났고, 후에 첸과 덩이 2명의 플레이어로 확장했다.[3][4]

정의

PPAD는 총계가 보장되는 FNP의 기능 문제 등급인 클래스 TFNP의 하위 집합이다.TFNP 공식 정의는 다음과 같다.

2진수 관계 P(x,y)는 P(x,y)가 x와 y를 모두 보유하는지 여부를 결정할 수 있는 결정론적 다항 시간 알고리즘이 있는 경우에만 TFNP에 있으며, 모든 x에 대해 P(x,y)가 보유하는 y가 존재한다.

TFNP의 하위 분류는 해결책이 항상 존재한다는 것을 증명하는 데 사용되는 수학적 증명 유형을 기반으로 정의된다.비공식적으로 PPAD는 P(x,y)가 보유하는 y가 존재한다는 보장이 지시된 그래프 상의 패리티 인수에 근거하는 TFNP의 하위 클래스다.클래스는 End-of-The-Line으로 알려진 완전한 문제 중 하나를 지정하여 공식적으로 정의된다.

G는 (아마도 기하급수적으로 큰) 지시 그래프로, 모든 꼭지점에는 전임자 하나와 후임자 하나가 있다.G는 정점 v의 전위 및 후위(존재하는 경우)를 반환하는 다항 시간 계산 함수 f(v)(v 크기의 다항식)를 주어 지정된다. 전임자가 없는 G의 정점 s를 주어 전위 또는 후위자가 없는 정점 t≠를 찾는다.(문제의 입력은 소스 정점 s와 함수 f(v)이다.즉, s 이외의 지시된 그래프의 출처나 싱크를 원한다.

G의 구조는 한 개의 이웃만 있는 정점이 쌍으로 나온다는 것을 의미하기 때문에, s가 있다면 그러한 t는 존재해야 한다.특히 s에 따라 s에서 시작하는 문자열의 다른 끝에서 그러한 t를 찾을 수 있다(f를 반복적으로 평가하기만 하면 지수적인 시간이 걸릴 수 있다는 점에 유의).

다른 복잡성 클래스와의 관계

PPAD는 TFNP에 포함된 (비방향 그래프에 대한 해당 패리티 인수 클래스) PPA에 포함되어 있지만, PPAD는 TFNP의 또 다른 하위 클래스인 (그러나 같지 않은) PPP에도 포함되어 있다.CLS를 함유하고 있다.[5]

PPAD는 어렵다고 여겨지는 문제의 한 종류지만, PPAD-완전성을 얻는 것은 NP-완전성을 얻는 것보다 난치성의 약한 증거다.PPAD 문제는 NP-완전할 수 없으며, 기술적인 이유로 NP는 의사결정 문제의 한 종류지만, PPAD 문제의 답은 항상 그렇다. 해결책이 존재한다고 알려져 있기 때문에, PPAD 문제는 그 해결책을 찾기가 어려울 수 있다.[6]그러나 PPAD와 NP는 밀접한 관련이 있다.주어진 게임에 내시 평형이 존재하느냐는 질문이 NP-하드일 수는 없지만, 그 답은 항상 그렇다, 두 번째 평형이 존재하느냐 하는 문제는 NP-완전하다.[7]PPAD가 FP와 같은 등급이고 그럴 가능성은 없어 보이지만 여전히 P ≠ NP가 있는 경우일 수 있다.[citation needed]PPAD 완전 문제의 예로는 내쉬 평형도 찾기, 브루워 함수에서 고정점 계산, 시장에서 화살-데브레 평형도 찾기 등이 있다.[8]

기타 주목할 만한 완전한 문제

주요 기사:PPAD 완료 문제 목록

참조

  1. ^ Christos Papadimitriou (1994). "On the complexity of the parity argument and other inefficient proofs of existence" (PDF). Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016/S0022-0000(05)80063-7. Archived from the original (PDF) on 2016-03-04. Retrieved 2008-03-08.
  2. ^ Fortnow, Lance (2005). "What is PPAD?". Retrieved 2007-01-29.
  3. ^ a b *Chen, Xi; Deng, Xiaotie (2006). Settling the complexity of two-player Nash equilibrium. Proc. 47th Symp. Foundations of Computer Science. pp. 261–271. doi:10.1109/FOCS.2006.69. ECCC TR05-140..
  4. ^ Daskalakis, Constantinos.; Goldberg, Paul W.; Papadimitriou, Christos H. (2009-01-01). "The Complexity of Computing a Nash Equilibrium". SIAM Journal on Computing. 39 (1): 195–259. doi:10.1137/070699652. ISSN 0097-5397.
  5. ^ Daskalakis, C.; Papadimitriou, C. (2011-01-23). Continuous Local Search. Proceedings. Society for Industrial and Applied Mathematics. pp. 790–804. CiteSeerX 10.1.1.362.9554. doi:10.1137/1.9781611973082.62. ISBN 9780898719932.
  6. ^ Scott Aaronson (2011). "Why philosophers should care about computational complexity". arXiv:1108.1791 [cs.CC].
  7. ^ Christos Papadimitriou (2011). "Lecture: Complexity of Finding a Nash Equilibrium" (PDF).
  8. ^ a b C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou (2009). "The Complexity of Computing a Nash Equilibrium". SIAM Journal on Computing. 39 (3): 195–259. CiteSeerX 10.1.1.152.7003. doi:10.1137/070699652.
  9. ^ Xi Chen and Xiaotie Deng (2006). "On the Complexity of 2D Discrete Fixed Point Problem". International Colloquium on Automata, Languages and Programming. pp. 489–500. ECCC TR06-037.
  10. ^ Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic Solutions for Envy-Free Cake Cutting". Operations Research. 60 (6): 1461. doi:10.1287/opre.1120.1116.