Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
PPAD (complexity)
open-in-new
<h2 id="definition">Definition</h2> <p>PPAD is a subset of the class <a href="/facts/TFNP/JwCmUwSV">TFNP</a>, the class of <a href="/facts/Function_problem/3zPWpraL">function problems</a> in <a href="/facts/FNP_(complexity)/m4MVkn3w">FNP</a> that are guaranteed to be <a href="/facts/Total_function/0vJMw0Nm">total</a>. The <a href="/facts/TFNP/JwCmUwSV">TFNP</a> formal definition is given as follows: </p> A binary relation P(<i>x</i>,<i>y</i>) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(<i>x</i>,<i>y</i>) holds given both <i>x</i> and <i>y</i>, and for every <i>x</i>, there exists a <i>y</i> such that P(<i>x</i>,<i>y</i>) holds. <p>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 <i>y</i> such that P(<i>x</i>,<i>y</i>) 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 <i>End-Of-The-Line</i>: </p> G is a (possibly exponentially large) directed graph with every <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> having at most one predecessor and at most one successor. G is specified by giving a polynomial-time computable function f(<i>v</i>) (polynomial in the size of <i>v</i>) that returns the predecessor and successor (if they exist) of the vertex <i>v</i>. Given a vertex <i>s</i> in G with no predecessor, find a vertex <i>t≠s</i> with no predecessor or no successor. (The input to the problem is the source vertex <i>s</i> and the function f(<i>v</i>)). In other words, we want any source or sink of the directed graph other than <i>s</i>. <p>Such a <i>t</i> must exist if an <i>s</i> does, because the structure of G means that vertices with only one neighbour come in pairs. In particular, given <i>s</i>, we can find such a <i>t</i> at the other end of the string starting at <i>s</i>. (Note that this may take exponential time if we just evaluate f repeatedly.) </p> <h2 id="relations-to-other-complexity-classes">Relations to other complexity classes</h2> <p>PPAD is contained in (but not known to be equal to) <a href="/facts/PPA_(complexity)/jTGW1rcp">PPA</a> (the corresponding class of parity arguments for <i>undirected</i> graphs) which is contained in TFNP. PPAD is also contained in (but not known to be equal to) <a href="/facts/PPP_(complexity)/ugPWJePY">PPP</a>, another subclass of TFNP. It contains <a href="http://people.csail.mit.edu/costis/CLS.pdf">CLS</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p><p>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 <a href="/facts/NP-completeness/NFPv56DU">NP-completeness</a>. 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.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> 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 <i>second</i> equilibrium exists is NP complete.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> Examples of PPAD-complete problems include finding <a href="/facts/Nash_equilibria/l74xzIHd">Nash equilibria</a>, computing fixed points in <a href="/facts/Brouwer_fixed-point_theorem/xP2p03lQ">Brouwer</a> functions, and finding <a href="/facts/Arrow%E2%80%93Debreu_model/MnxUyNFr">Arrow-Debreu equilibria</a> in markets.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>Fearnley, Goldberg, Hollender and Savani<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> proved that a complexity class called CLS is equal to the intersection of PPAD and <a href="/facts/PLS_(complexity)/s4QGR4f2">PLS</a>. </p> <h2 id="further-reading">Further reading</h2> <ul><li>Equilibria, fixed points, and complexity classes: a survey.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></li></ul> <h2 id="other-notable-complete-problems">Other notable complete problems</h2> <p class="note">Main article: <a href="/facts/List_of_PPAD-complete_problems/kgmSc4Gn">List of PPAD-complete problems</a></p> <ul><li>Finding the <a href="/facts/Nash_equilibrium/l74xzIHd">Nash equilibrium</a> on a 2-player game<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> or the <a href="/facts/Epsilon-equilibrium/LR9jWpPH">Epsilon-equilibrium</a> on a game with any number of players.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li></ul> <ul><li>Finding a three-colored point in <a href="/facts/Sperner%27s_Lemma/kLbeQFyY">Sperner's Lemma</a>.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li> <li>Finding an <a href="/facts/Envy-free_cake-cutting/dWXkFjGa">envy-free cake-cutting</a> when the utility functions are given by polynomial-time algorithms.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Fortnow, Lance (2005). "What is PPAD?". Retrieved 2007-01-29. <a href="/wiki/Lance_Fortnow" target="_blank">/wiki/Lance_Fortnow</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>*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.. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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. CiteSeerX 10.1.1.152.7003. doi:10.1137/070699652. ISSN 0097-5397. <a href="https://epubs.siam.org/doi/10.1137/070699652" target="_blank">https://epubs.siam.org/doi/10.1137/070699652</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. S2CID 2056144. <a href="9780898719932" target="_blank">9780898719932</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Scott Aaronson (2011). "Why philosophers should care about computational complexity". arXiv:1108.1791 [cs.CC]. <a href="/wiki/Scott_Aaronson" target="_blank">/wiki/Scott_Aaronson</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Christos Papadimitriou (2011). "Lecture: Complexity of Finding a Nash Equilibrium" (PDF). <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Fearnley, John; Goldberg, Paul; Hollender, Alexandros; Savani, Rahul (2022-12-19). "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS". Journal of the ACM. 70 (1): 7:1–7:74. arXiv:2011.01929. doi:10.1145/3568163. ISSN 0004-5411. S2CID 263706261. <a href="https://doi.org/10.1145/3568163" target="_blank">https://doi.org/10.1145/3568163</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Yannakakis, Mihalis (2009-05-01). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. arXiv:0802.2831. doi:10.1016/j.cosrev.2009.03.004. ISSN 1574-0137. <a href="https://www.sciencedirect.com/science/article/pii/S1574013709000161" target="_blank">https://www.sciencedirect.com/science/article/pii/S1574013709000161</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>*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.. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>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. <a href="/wiki/Christos_Papadimitriou" target="_blank">/wiki/Christos_Papadimitriou</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>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. <a href="/wiki/Xi_Chen" target="_blank">/wiki/Xi_Chen</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>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. S2CID 4430655. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> </ol>