ON THE GROUND STATE STRUCTURE OF P AND NP-COMPLETE RANDOM DECISION PROBLEMS
- 10 January 1999
- journal article
- Published by World Scientific Pub Co Pte Ltd in Modern Physics Letters B
- Vol. 13 (1) , 1-12
- https://doi.org/10.1142/s0217984999000026
Abstract
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.Keywords
This publication has 3 references indexed in Scilit:
- Entropy of theK-Satisfiability ProblemPhysical Review Letters, 1996
- Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 1994
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960