We resolve the question of the complexity of Nash equilibrium by
showing that the problem of computing a Nash equilibrium in a game
with 4 or more players is complete for the complexity class PPAD.
Our proof uses ideas from the recently-established equivalence
between polynomial-time solvability of normal-form games and
graphical games, and shows that these kinds of games can implement
arbitrary members of a PPAD-complete class of Brouwer functions.