Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ESS is an important refinement of the ESS concept which has also been studied extensively and is further motivated by Harsanyi's result that "almost all" strategic form games contain only regular equilibria.

There is a substantial literature on computing evolutionarily stable strategies, yet despite these efforts the precise computational complexity of determining the existence of an ESS in a game has remained elusive, although it has been speculated by some that the problem is NP-hard.

In this paper we show that determining the existence of an ESS is both NP-hard and coNP-hard, and that it is contained in \Sigma^P_2, the second level of the polynomial time hierarchy. On the other hand, we show that determining the existence of a regular ESS is indeed NP-complete. Our upper bounds also yield algorithms for computing a (regular) ESS, if one exists, with the same complexities.

Our upper bounds combine known criteria for the existence of an ESS based on quadratic forms, together with known results about the complexity of quadratic programming decision problems. Our lower bounds employ, among other things, a classic characterization
of maximum clique size via quadratic programming.