Fri Dec 12, 2014
60 Evans Hall, 4–6 PM
Christos Papadimitriou (UC Berkeley)
Exponential existence proofs and complexity
Many computational problems in NP have the property that a solution is guaranteed to exist for every instance, and yet these problems do not seem to belong in P. Examples are factoring, Nash equilibrium, finding a short vector in a lattice, or a prime in [n, 2n], among many others. Such problems can be categorized by the corresponding existence proof. Rather surprisingly, it turns out that, in all known cases, this existence proof contains a simple graph-theoretic argument (such as “every graph has an even number of odd nodes,” or “every directed acyclic graph has a sink” or the pigeonhole principle) albeit applied to an exponentially large graph. Several natural problems are known to be complete for the corresponding classes. I shall introduce and discuss this intriguing aspect of complexity theory, including certain recent developments.