Gabriel Istrate, Stephan Boettcher and Allon Percus. Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity. Annals of Mathematics and Artificial Intelligence, 44 (4), pp. 353  372, 2005.
Abstract:
We prove a result displaying a connection between the existence of a phase transition in combinatorial problems and the complexity of decision algorithms.
Specifically, for the class of generalized random satisfiability problems we prove that a discontinuity in a variant (called spine) of the order parameter used in the study of phase transitions in such problems is accompanied by an exponential lower bound on the complexity of resolution proofs (and DavisPutnam algorithms) for such problems. The two phenomena have a common underlying cause: a linear lower bound on the size of the minimally unsatisfiable subformulas of random formulas at the satisfiability phase transition.
A second goal of the paper is to obtain a classification of generalized random satisfiability problems with a discontinuous spine/exponential resolution complexity. Several results formalize the intuition that problems with a continuous spine "qualitatively resemble random 2satisfiability".
Finally, we provide some empirical evidence that the spine (and NOT the order parameter arising from considerations from Statistical Mechanics) is the parameter that has an impact on the complexity of (some classes of) decision problems. In other words, the connection between phase transitions in combinatorial problems and the complexity of decision algorithms can be expressed in purely combinatorial terms, devoid of any Statistical Mechanics considerations.
A preliminary version of this paper has appeared in the Proceedings of the Eighth International Symposium on Artificial Intelligence and Mathematics, 2004, and can be read from
http://xxx.lanl.gov/abs/cs.CC/0503082
Keywords:
phase transitions in combinatorial problems, proof complexity
URL:
http://www.springerlink.com/link.asp?id=n6501173nh6w8140
Posted by
Gabriel Istrate
Back
