We study the computational complexity of deciding the existence of a
Pure Nash Equilibrium in multi-player strategic games.
We address two fundamental questions: how can we represent a game?, and
how can we represent a game with polynomial pay-off functions?
Our results show that the computational complexity of
deciding the existence of a pure Nash equilibrium in an strategic game
depends on two parameters: the number of players and the size of the
sets of strategies. In particular we show that deciding the existence
of a Nash equilibrium in an strategic game is NP-complete when the
number of players is large and the number of strategies for each
player is constant, while the problem is $\Sigma_2^p$-complete when the number
of players is a constant and the size of the sets of strategies is
exponential (with respect to the length of the strategies).