|
|
|
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 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.
|
|
|
|