238:. PPAD problems cannot be NP-complete, for the technical reason that NP is a class of decision problems, but the answer of PPAD problems is always yes, as a solution is known to exist, even though it might be hard to find that solution. However, PPAD and NP are closely related. While the question whether a Nash equilibrium exists for a given game cannot be NP-hard because the answer is always yes, the question whether a
127:
Subclasses of TFNP are defined based on the type of mathematical proof used to prove that a solution always exists. Informally, PPAD is the subclass of TFNP where the guarantee that there exists a
756:
432:
234:
PPAD is a class of problems that are believed to be hard, but obtaining PPAD-completeness is a weaker evidence of intractability than that of obtaining
344:
139:) holds is based on a parity argument on a directed graph. The class is formally defined by specifying one of its complete problems, known as
527:
39:
based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of
292:
51:
for PPAD by
Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players.
151:
having at most one predecessor and at most one successor. G is specified by giving a polynomial-time computable function f(
815:
251:
195:
does, because the structure of G means that vertices with only one neighbour come in pairs. In particular, given
247:
91:) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(
40:
255:
614:
600:
575:
505:
464:
340:
319:
32:
367:
148:
48:
700:
262:
619:
510:
469:
303:
791:
712:
681:
655:
555:
533:
312:
730:
673:
523:
482:
223:
graphs) which is contained in TFNP. PPAD is also contained in (but not known to be equal to)
783:
722:
665:
624:
579:
515:
474:
424:
359:
299:
270:
224:
216:
68:
64:
44:
28:
20:
243:
235:
774:
Deng, X.; Qi, Q.; Saberi, A. (2012). "Algorithmic
Solutions for Envy-Free Cake Cutting".
551:
451:
Daskalakis, Constantinos.; Goldberg, Paul W.; Papadimitriou, Christos H. (2009-01-01).
72:
395:
363:
242:
equilibrium exists is NP complete. Examples of PPAD-complete problems include finding
809:
685:
391:
345:"On the complexity of the parity argument and other inefficient proofs of existence"
171:
with no predecessor or no successor. (The input to the problem is the source vertex
795:
642:
Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19).
537:
751:
and
Xiaotie Deng (2006). "On the Complexity of 2D Discrete Fixed Point Problem".
726:
504:. Proceedings. Society for Industrial and Applied Mathematics. pp. 790–804.
207:. (Note that this may take exponential time if we just evaluate f repeatedly.)
179:)). In other words, we want any source or sink of the directed graph other than
760:
519:
452:
436:
261:
Fearnley, Goldberg, Hollender and Savani proved that a complexity class called
734:
677:
486:
228:
787:
159:) that returns the predecessor and successor (if they exist) of the vertex
428:
748:
554:(2011). "Why philosophers should care about computational complexity".
628:
478:
423:. Proc. 47th Symp. Foundations of Computer Science. pp. 261–271.
605:
669:
660:
322:
when the utility functions are given by polynomial-time algorithms.
717:
643:
560:
147:
G is a (possibly exponentially large) directed graph with every
76:
60:
36:
753:
International
Colloquium on Automata, Languages and Programming
282:
Equilibria, fixed points, and complexity classes: a survey.
603:(2009). "The Complexity of Computing a Nash Equilibrium".
27:("Polynomial Parity Arguments on Directed graphs") is a
644:"The Complexity of Gradient Descent: CLS = PPAD ∩ PLS"
421:
Settling the complexity of two-player Nash equilibrium
215:
PPAD is contained in (but not known to be equal to)
580:"Lecture: Complexity of Finding a Nash Equilibrium"
701:"Equilibria, fixed points, and complexity classes"
219:(the corresponding class of parity arguments for
594:
592:
500:Daskalakis, C.; Papadimitriou, C. (2011-01-23).
453:"The Complexity of Computing a Nash Equilibrium"
43:because it contains the problem of computing a
8:
203:at the other end of the string starting at
413:
411:
716:
659:
618:
559:
509:
468:
227:, another subclass of TFNP. It contains
167:in G with no predecessor, find a vertex
352:Journal of Computer and System Sciences
332:
79:formal definition is given as follows:
306:on a game with any number of players.
211:Relations to other complexity classes
7:
699:Yannakakis, Mihalis (2009-05-01).
14:
599:C. Daskalakis, P.W. Goldberg and
311:Finding a three-colored point in
419:Chen, Xi; Deng, Xiaotie (2006).
265:is equal to the intersection of
287:Other notable complete problems
47:: this problem was shown to be
35:in 1994. PPAD is a subclass of
293:List of PPAD-complete problems
59:PPAD is a subset of the class
1:
364:10.1016/S0022-0000(05)80063-7
155:) (polynomial in the size of
727:10.1016/j.cosrev.2009.03.004
832:
520:10.1137/1.9781611973082.62
302:on a 2-player game or the
290:
71:that are guaranteed to be
606:SIAM Journal on Computing
457:SIAM Journal on Computing
705:Computer Science Review
502:Continuous Local Search
256:Arrow-Debreu equilibria
254:functions, and finding
41:algorithmic game theory
788:10.1287/opre.1120.1116
576:Christos Papadimitriou
341:Christos Papadimitriou
320:envy-free cake-cutting
248:computing fixed points
33:Christos Papadimitriou
199:, we can find such a
755:. pp. 489–500.
429:10.1109/FOCS.2006.69
83:A binary relation P(
776:Operations Research
304:Epsilon-equilibrium
175:and the function f(
99:) holds given both
816:Complexity classes
648:Journal of the ACM
601:C.H. Papadimitriou
629:10.1137/070699652
479:10.1137/070699652
191:must exist if an
163:. Given a vertex
111:, there exists a
65:function problems
823:
800:
799:
771:
765:
764:
745:
739:
738:
720:
696:
690:
689:
663:
639:
633:
632:
622:
596:
587:
586:
584:
572:
566:
565:
563:
548:
542:
541:
513:
497:
491:
490:
472:
448:
442:
440:
415:
406:
405:
403:
402:
388:
382:
381:
379:
378:
372:
366:. Archived from
349:
337:
300:Nash equilibrium
107:, and for every
45:Nash equilibrium
29:complexity class
21:computer science
16:Complexity class
831:
830:
826:
825:
824:
822:
821:
820:
806:
805:
804:
803:
773:
772:
768:
747:
746:
742:
698:
697:
693:
670:10.1145/3568163
654:(1): 7:1–7:74.
641:
640:
636:
620:10.1.1.152.7003
598:
597:
590:
582:
574:
573:
569:
550:
549:
545:
530:
511:10.1.1.362.9554
499:
498:
494:
470:10.1.1.152.7003
450:
449:
445:
418:
416:
409:
400:
398:
396:"What is PPAD?"
390:
389:
385:
376:
374:
370:
347:
339:
338:
334:
329:
313:Sperner's Lemma
295:
289:
279:
277:Further reading
244:Nash equilibria
236:NP-completeness
213:
141:End-Of-The-Line
63:, the class of
57:
17:
12:
11:
5:
829:
827:
819:
818:
808:
807:
802:
801:
766:
740:
691:
634:
613:(3): 195–259.
588:
567:
552:Scott Aaronson
543:
528:
492:
463:(1): 195–259.
443:
407:
392:Fortnow, Lance
383:
358:(3): 498–532.
331:
330:
328:
325:
324:
323:
316:
308:
307:
291:Main article:
288:
285:
284:
283:
278:
275:
212:
209:
185:
184:
125:
124:
56:
53:
31:introduced by
15:
13:
10:
9:
6:
4:
3:
2:
828:
817:
814:
813:
811:
797:
793:
789:
785:
781:
777:
770:
767:
762:
758:
754:
750:
744:
741:
736:
732:
728:
724:
719:
714:
710:
706:
702:
695:
692:
687:
683:
679:
675:
671:
667:
662:
657:
653:
649:
645:
638:
635:
630:
626:
621:
616:
612:
608:
607:
602:
595:
593:
589:
581:
577:
571:
568:
562:
557:
553:
547:
544:
539:
535:
531:
529:9780898719932
525:
521:
517:
512:
507:
503:
496:
493:
488:
484:
480:
476:
471:
466:
462:
458:
454:
447:
444:
438:
434:
430:
426:
422:
414:
412:
408:
397:
393:
387:
384:
373:on 2016-03-04
369:
365:
361:
357:
353:
346:
342:
336:
333:
326:
321:
317:
314:
310:
309:
305:
301:
297:
296:
294:
286:
281:
280:
276:
274:
272:
268:
264:
259:
257:
253:
249:
245:
241:
237:
232:
230:
226:
222:
218:
210:
208:
206:
202:
198:
194:
190:
182:
178:
174:
170:
166:
162:
158:
154:
150:
146:
145:
144:
142:
138:
134:
130:
122:
118:
114:
110:
106:
102:
98:
94:
90:
86:
82:
81:
80:
78:
74:
70:
66:
62:
54:
52:
50:
46:
42:
38:
34:
30:
26:
22:
779:
775:
769:
752:
743:
711:(2): 71–85.
708:
704:
694:
651:
647:
637:
610:
604:
570:
546:
501:
495:
460:
456:
446:
420:
399:. Retrieved
386:
375:. Retrieved
368:the original
355:
351:
335:
298:Finding the
266:
260:
258:in markets.
239:
233:
220:
214:
204:
200:
196:
192:
188:
186:
180:
176:
172:
168:
164:
160:
156:
152:
140:
136:
132:
131:such that P(
128:
126:
120:
116:
115:such that P(
112:
108:
104:
100:
96:
92:
88:
84:
58:
24:
18:
782:(6): 1461.
318:Finding an
661:2011.01929
401:2007-01-29
377:2008-03-08
327:References
221:undirected
55:Definition
735:1574-0137
718:0802.2831
686:263706261
678:0004-5411
615:CiteSeerX
561:1108.1791
506:CiteSeerX
487:0097-5397
465:CiteSeerX
810:Category
761:TR06-037
578:(2011).
437:TR05-140
394:(2005).
343:(1994).
123:) holds.
49:complete
796:4430655
749:Xi Chen
538:2056144
252:Brouwer
187:Such a
794:
759:
733:
684:
676:
617:
536:
526:
508:
485:
467:
435:
240:second
149:vertex
75:. The
792:S2CID
713:arXiv
682:S2CID
656:arXiv
583:(PDF)
556:arXiv
534:S2CID
371:(PDF)
348:(PDF)
73:total
757:ECCC
731:ISSN
674:ISSN
524:ISBN
483:ISSN
433:ECCC
269:and
267:PPAD
103:and
77:TFNP
61:TFNP
37:TFNP
25:PPAD
784:doi
723:doi
666:doi
625:doi
516:doi
475:doi
425:doi
360:doi
271:PLS
263:CLS
250:in
229:CLS
225:PPP
217:PPA
169:t≠s
69:FNP
67:in
19:In
812::
790:.
780:60
778:.
729:.
721:.
707:.
703:.
680:.
672:.
664:.
652:70
650:.
646:.
623:.
611:39
609:.
591:^
532:.
522:.
514:.
481:.
473:.
461:39
459:.
455:.
431:.
410:^
356:48
354:.
350:.
273:.
246:,
231:.
143::
23:,
798:.
786::
763:.
737:.
725::
715::
709:3
688:.
668::
658::
631:.
627::
585:.
564:.
558::
540:.
518::
489:.
477::
441:.
439:.
427::
417:*
404:.
380:.
362::
315:.
205:s
201:t
197:s
193:s
189:t
183:.
181:s
177:v
173:s
165:s
161:v
157:v
153:v
137:y
135:,
133:x
129:y
121:y
119:,
117:x
113:y
109:x
105:y
101:x
97:y
95:,
93:x
89:y
87:,
85:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.