Necklace Splitting and Natural PPA-Complete Problems

23^rd October 2019, 14:00
Aris Filos-Ratsikas
University of Liverpool

Abstract

The class TFNP was defined by Meggido and Papadimitriou in 1991 and contains total search problems, i.e., problems for which a solution always exists and is verifiable in polynomial time. Among its many subclasses, defined by Papadimitriou in 1994 (as well as in subsequent works), PPAD has been largely successful in capturing the computational complexity of many interesting problems, with the most prominent example being the PPAD-completeness of computing a Nash equilibrium. On the other hand, the class PPA was not known to have any natural complete problems. In this talk, I will go present some recent work (with Paul Goldberg), in which we identify the first natural PPA-complete problems. It turns out that one of them is the well-known Necklace Splitting problem (Alon 1987) from mathematics, the complexity of which was posed as an open question several times over the years.

The talk will not be very technical and will also serve as a brief introduction to the subclasses of TFNP for a wider audience.