Johan Thapper
From Mean Payoff Games to Arithmetic Circuit Evaluation

The computational complexity of deciding the winner in a Mean Payoff Game
(MPG) has been open for over 30 year. Recently, this problem has been
linked to a constraint satisfaction problem called the max-atoms problem.
We will review a reduction by Schewe from MPG, essentially via the
max-atoms problem, to linear programming in the real unit-cost model. We
also make the observation that in order to solve MPG, one additionally
needs to solve the problem of deciding whether an arithmetic circuit
evaluates to a non-negative number.