# Why is computing pure Nash equilibria NP-complete?

In this paper, it is claimed that computing pure-strategy Nash equilibria of games in standard normal form is NP-complete.

This confuses me, because I do not understand why it is hard to guess the right strategy profile (the authors call this the "global strategy") for a game. Surely if the Nash equilibrium of a game is written out in normal form, where every strategy profile is assigned its own cell, then it should take only linear time to run through every possible strategy profile that is a candidate for being a Nash equilibrium.

I do not understand what I am missing; please explain why Nash equilibrium computation is hard for standard normal form games. Thank you.

• You might want to also refer to the full version of the paper, published at JAIR jair.org/papers/paper1683.html (For some reason Google Scholar can't deal with the distributed, electronic-only format of JAIR so it tends to be de-emphasized in its results.) – András Salamon Jul 6 '14 at 10:42

In general, if each of $n$ players has $m$ actions then the the strategic form has $nm^n$ entries, but a graphical game has $O(nm^{d+1})$, where $d$ is the maximum degree in the graph. So for constant $d$, the graphical game representation is exponentially smaller than the strategic form. In their reduction $d$ can be 3 (and $m$ can also be 3, so only $n$ needs to vary).