Complexity of Total Search Problems

Basic Information

Description: 
The class FNP (for Function NP) contains all search problems whose decision version is in NP. Such problems, in addition to a “yes/no” answer, ask for a witness in case the answer is “yes.” Evidently, there are search problems whose decision version is always “yes”: computing a mixed Nash equilibrium, computing a pure Nash equilibrium in potential games, or computing a consensus-halving, are all problems that have at least one solution. Are these problems as hard as other problems in FNP for which the existence of a solution is not guaranteed? To answer this question, a subclass of FNP called TFNP (for Total Function NP) was defined in 1989. We will study the most well-known subclasses of TFNP, such as PPAD, PPA, PLS, and PPP, and explore many important problems that are complete for some of these classes. These problems come from algorithmic game theory, fair division, local optimization, or cryptography.

Recommended reading: Original research articles

Prerequisites: Basic knowledge of computational complexity

Information: Participants will be assigned research papers and are expected to deliver a presentation, demonstrating in-depth understanding of the discussed problem, key technical ideas and proofs, related bibliography, and open questions.