Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity

Gabriel Istrate, Stefan Boettcher, Allon G. Percus

We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a…