PPA (complexity)
{{Short description|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{{cite journal | author = Christos Papadimitriou | year = 1994 | title = On the complexity of the parity argument and other inefficient proofs of existence | journal = Journal of Computer and System Sciences | volume = 48 | issue = 3 | pages = 498–532 | url = http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf | doi = 10.1016/S0022-0000(05)80063-7 | access-date = 2009-12-19 | archive-url = https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf | archive-date = 2016-03-04 | url-status = dead }} (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 -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.
Related classes
PPAD is defined in a similar way to PPA, except that it is defined on directed graphs. PPAD 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).
Examples
- There is an un-oriented version of the Sperner lemma known to be complete for PPA.{{cite journal | author = Michelangelo Grigni | year = 1995 | title = A Sperner Lemma Complete for PPA | journal = Information Processing Letters | volume = 77 | issue = 5–6 | pages = 255–259 | doi = 10.1016/S0020-0190(00)00152-6| citeseerx = 10.1.1.63.9463 }}
- The consensus-halving problem is known to be complete for PPA.{{cite conference |author1=A. Filos-Ratsikas |author2=P.W. Goldberg | title = Consensus-Halving is PPA-Complete | book-title = Proc. of 50th Symposium on Theory of Computing | year = 2018 | pages = 51–64 | DOI = 10.1145/3188745.3188880 | arxiv = 1711.04503 }}
- 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.{{cite journal | author = E. Jeřábek | title = Integer Factoring and Modular Square Roots | journal = Journal of Computer and System Sciences | year = 2016 | volume = 82 | issue = 2 | pages = 380–394 | doi = 10.1016/j.jcss.2015.08.001 | arxiv = 1207.5220 }}
References
{{reflist}}