Structural results for total search complexity classes with applications to game theory and optimisation

Thesis

While the celebrated theory of NP-completeness has been very successful in explaining the intractability of many interesting problems, there still remain many natural and seemingly hard problems that are not known to be NP-hard. Several of these problems lie in the class of total NP search problems (TFNP), namely the class of NP search problems that always have a solution. Importantly, these problems cannot be NP-hard unless NP = co-NP. Notable examples of TFNP problems include FACTORING (given a natural number, compute its prime factorisation) and NASH (given a game, compute a mixed Nash equilibrium). In order to shed light on the complexity of these problems, researchers have attempted to classify them in various subclasses of TFNP such as PPAD, PPA, PPP, PLS, and CLS. A celebrated result in this line of research is the PPAD-completeness of NASH, yielding strong evidence that the problem is not polynomial-time solvable.

In this thesis we provide new structural results for TFNP subclasses and show how they can be used to classify natural problems arising from application areas such as game theory and optimisation. In the first part of this work, we construct more powerful tools for proving membership in PPAD, as well as PPAD-hardness. We directly apply these tools to show that the Hairy Ball theorem from topology ("you can't comb a hairy ball flat without creating a cowlick"), as well as the equilibrium computation problem in First Price Auctions with subjective priors, are both PPAD-complete.

In the second part of this thesis, we present our main result: the collapse CLS = PPAD ∩ PLS. We prove this surprising collapse by exhibiting the first non-artificial PPAD ∩ PLS-complete problem - a problem arising naturally from the famous gradient descent algorithm. Our result puts PPAD ∩ PLS on the map as a TFNP subclass that captures the complexity of natural problems.

In the third and final part, we provide various structural results for the classes PPA-k (corresponding to arguments modulo k), including the first topological characterisations of these classes. As a direct application, we prove that NECKLACE-SPLITTING with k thieves - a notorious problem in combinatorics and fair division - lies in PPA-k under Turing reductions.

Authors: Hollender, A

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: computational complexity; TFNP
• Subjects: Computational Complexity; Theoretical Computer Science