We are interested in the complexity of finding Nash equilibria with one uniformly mixed strategy (that is, equilibria in which at least one of the players plays a uniform probability distribution over some set of pure strategies). We show that, even in imitation bimatrix games, where one player has a positive payoff if he plays the same pure strategy as the opponent, deciding the existence of such an equilibrium is an
-complete problem. We derive this result from the
-completeness of graph-theoretical problems strictly related to this class of equilibria.