Surf Wiki
Save to docs
general/complexity-classes

From Surf Wiki (app.surf) — the open knowledge base

PPA (complexity)

Complexity class

Complexity class

In computational complexity theory, PPA is a complexity class, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou in 1994 (page 528), PPA is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the handshaking lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem).

Definition

PPA is defined as follows. Suppose we have a graph on whose vertices are 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 polynomial-time reduction to this graph search problem. A problem is complete for the class PPA if in addition, this graph search problem is reducible to that problem.

Examples

  • There is an un-oriented version of the Sperner lemma known to be complete for PPA.
  • The consensus-halving problem is known to be complete for PPA.
  • The problem of searching for a second Hamiltonian cycle on a 3-regular graph is a member of PPA, but is not known to be complete for PPA.
  • There is a randomized polynomial-time reduction from the problem of integer factorization to problems complete for PPA.

References

References

  1. Christos Papadimitriou. (1994). "On the complexity of the parity argument and other inefficient proofs of existence". [[Journal of Computer and System Sciences]].
  2. Michelangelo Grigni. (1995). "A Sperner Lemma Complete for PPA". [[Information Processing Letters]].
  3. (2018). "Consensus-Halving is PPA-Complete".
  4. E. Jeřábek. (2016). "Integer Factoring and Modular Square Roots". [[Journal of Computer and System Sciences]].
Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

complexity-classes
Want to explore this topic further?

Ask Mako anything about PPA (complexity) — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report