The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches

The complexity classes PPA and PPAD were introduced in a seminal paper of Papadimitriou [47] in 1994, in an attempt to classify several natural problems in the class TFNP [45]. TFNP is the class of total search problems in NP for which a solution exists for every instance and the solution can be efficiently verified. Various important problems were subsequently proven to be complete for the class PPAD, such as the complexity of many versions of Nash equilibrium [16, 11, 21, 46, 50, 12] and market equilibrium computation [15, 9, 57, 13, 52]. For details on this, and the significance of PPAcompleteness, see the related discussion in [23], but note the following basic points. As evidence of computational hardness, PPA-completeness is stronger than PPAD-completeness: PPAD PPA. In terms of expressive power, the distinction is that PPA-complete problems can embed a search for a guaranteed fixpoint in a non-oriented topological space, but PPAD problems restrict us to an oriented one. Complete problems for the class PPA seemed to be much more elusive than PPAD-complete ones, especially when one is interested in "natural" problems, where "natural" here has the very specific meaning of problems that do not explicitly contain a circuit in their definition.