PPA (complexity)

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.

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).

• The problem LONELY is PPA-complete: given a circuit that defines a partial matching on such that is unmatched (these conditions can be syntactically enforced by manipulating the circuit), find another unmatched vertex.
• 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.