Structural results for total search complexity classes with applications to game theory and optimisation - Hollender, A (2021)
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.