Christos H. Papadimitriou: Computation and Intractability: Echoes of Kurt Gödel


Even though the Incompleteness Theorem has no explicit computational agenda or direct implication, it can be considered the birth of the computer era - and not just because of the nature of its influential proof: The abstract computing machines that haunted the minds of mathematicians the world around a few years later (and were incarnated a decade hence) were conceived for the express purpose of strengthening the theorem in an algorithmic direction. Ten more years later, in 1956, it was Gödel who, in a letter to a terminally sick von Neumann, identified the P vs NP question, not yet as the quintessence of computational intractability, but as the only remaining aspect of the Foundations quest that had not yet been ruled out - namely, the possibility that proofs can be mechanically discovered efficiently, with "efficiency" understood relative to the proof's length. In another Princeton office during the same decade, Nash had proved, by a reduction to Brouwer's fixpoint theorem, that every game has a mixed equilibrium. A reduction in the opposite direction was recently discovered by Constantinos Daskalakis, Paul W. Goldberg, and the speaker, establishing that computing Nash equilibria in a normal-form game is intractable. Gödel's influence can be identified in this proof too: The reduction relies crucially on a variant of arithmetization in which a player's mixture of two strategies is considered a real number, and games are designed that add, multiply, and compare.