Spines of Random Constraint Satisfaction Problems: Definition and Impact on Computational Complexity.
Stefan Boettcher, Gabriel Istrate, Allon G. Percus · 2004
The major promise of phase transitions in combinatorial problems was to shed light on the “practical” algorithmic complexity of combinatorial problems. A possible connection has been highlighted by the results (based on experimental evidence and nonrigorous arguments from statistical mechanics) of Monasson