  We establish that the subgame perfect equilibrium (SPE) threshold problem for
mean-payoff games is NP-complete. While the SPE threshold problem was recently
shown to be decidable (in doubly exponential time) and NP-hard, its exact worst
case complexity was left open.
