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.