


Christos H. Papadimitriou: Computation and Intractability: Echoes of Kurt Gödel
Abstract
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 normalform 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.



