Minimax Games, Spin Glasses and the Polynomial-Time Hierarchy of Complexity Classes

Peter Varga

We use the negative replica method, which was originally developed for the study of overfrustation in disordered system, to investigate the statistical behaviour of the cost functi…