ON THE GROUND STATE STRUCTURE OF P AND NP-COMPLETE RANDOM DECISION PROBLEMS
Antonio S. Gliozzi, Riccardo Zecchina · Modern Physics Letters B · 1999
The structure of the space of solutions of a prototype model of complexity theory and random structures is analyzed. Depending on a single control parameter, the model interpolates between different complexity classes and is known to undergo continuous as well as discontinuous phase transitions. Some geometrical aspects of such a symmetry breaking phenomena are studied analytically and numerically, and a simple conjecture for the onset of exponential regimes in recursive search algorithms is discussed.