PPA (complexity)

<h2 id="definition">Definition</h2>
<p>PPA is defined as follows. Suppose we have a graph on whose vertices are 
  
    
      
        n
      
    
    {\displaystyle n}
  
-bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently perform local exploration.) Suppose furthermore that a specific vertex (say the all-zeroes vector) has an odd number of neighbors. We are required to find another odd-degree vertex. Note that this problem is in NP—given a solution it may be verified using the circuit that the solution is correct.  A function computation problem belongs to PPA if it admits a <a href="/facts/Polynomial-time_reduction/bBvfFxyM">polynomial-time reduction</a> to this graph search problem. A problem is <a href="/facts/Complete_(complexity)/Ine1b8Qy">complete</a> for the class PPA if in addition, this graph search problem is reducible to that problem.
</p>
<h2 id="related-classes">Related classes</h2>
<p><a href="/facts/PPAD_(complexity)/EKaF3W9c">PPAD</a> is defined in a similar way to PPA, except that it is defined on <i>directed</i> graphs. <a href="/facts/PPAD_(complexity)/EKaF3W9c">PPAD</a> is a subclass of PPA. This is because the corresponding problem that defines PPAD, known as END OF THE LINE, can be reduced (in a straightforward way) to the above search for an additional odd-degree vertex (essentially, just by ignoring the directions of the edges in END OF THE LINE).
</p>
<h2 id="examples">Examples</h2>
<ul><li>There is an un-oriented version of the Sperner lemma known to be complete for PPA.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li>
<li>The <a href="/facts/Consensus_halving/URtpaecA">consensus-halving</a> problem is known to be complete for PPA.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li>
<li>The problem of searching for a second <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycle</a> on a 3-regular graph is a member of PPA, but is not known to be complete for PPA.</li>
<li>There is a randomized polynomial-time reduction from the problem of <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a> to problems complete for PPA.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</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 2009-12-19. <a href="https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" target="_blank">https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Michelangelo Grigni (1995). "A Sperner Lemma Complete for PPA". Information Processing Letters. 77 (5–6): 255–259. CiteSeerX 10.1.1.63.9463. doi:10.1016/S0020-0190(00)00152-6. <a href="/wiki/Information_Processing_Letters" target="_blank">/wiki/Information_Processing_Letters</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>A. Filos-Ratsikas; P.W. Goldberg (2018). "Consensus-Halving is PPA-Complete". Proc. of 50th Symposium on Theory of Computing. pp. 51–64. arXiv:1711.04503. doi:10.1145/3188745.3188880. <a href="/wiki/Symposium_on_Theory_of_Computing" target="_blank">/wiki/Symposium_on_Theory_of_Computing</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>E. Jeřábek (2016). "Integer Factoring and Modular Square Roots". Journal of Computer and System Sciences. 82 (2): 380–394. arXiv:1207.5220. doi:10.1016/j.jcss.2015.08.001. <a href="/wiki/Journal_of_Computer_and_System_Sciences" target="_blank">/wiki/Journal_of_Computer_and_System_Sciences</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

PPA (complexity) open-in-new

PPA (complexity)