Event Detail

Fri Dec 12, 2014
60 Evans Hall, 4–6 PM
Logic Colloquium
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.