Minimax games, spin glasses, and the polynomial-time hierarchy of complexity classes
- 1 June 1998
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 57 (6) , 6487-6492
- https://doi.org/10.1103/physreve.57.6487
Abstract
We use the negative replica method, which was originally developed for the study of overfrustation in disordered systems, to investigate the statistical behavior of the cost function of minimax games. These games are treated as hierarchical statistical mechanical systems, in which one of the components is at negative temperature.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Partially annealed neural networksJournal of Physics A: General Physics, 1994
- Partial annealing and overfrustration in disordered systemsJournal of Physics A: General Physics, 1994
- Coupled dynamics of fast spins and slow interactions in neural networks and spin systemsJournal of Physics A: General Physics, 1993
- Physics of the spin-glass statePhysics-Uspekhi, 1993
- Application of statistical mechanics to NP-complete problems in combinatorial optimisationJournal of Physics A: General Physics, 1986
- A replica analysis of the travelling salesman problemJournal de Physique, 1986
- Games against natureJournal of Computer and System Sciences, 1985
- Replicas and optimizationJournal de Physique Lettres, 1985
- Optimization by Simulated AnnealingScience, 1983
- Toward a mean field theory for spin glassesPhysics Letters A, 1979