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

We provide a compendium of problems that are complete for symmetric logarithmic space (SL). Complete problems are one method of studying this class for which programming is nonintuitive. A number of the problems in the list were not previously known to be complete. A list containing a variety of open ... more >>>