Autori: Gabriel Istrate, Stephan Boettcher and Allon Percus

Editorial: Annals of Mathematics and Artificial Intelligence, 44 (4), p.353 - 372, 2005.

Rezumat:

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 Davis-Putnam 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 2-satisfiability”.

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

Cuvinte cheie: phase transitions in combinatorial problems, proof complexity

URL: http://www.springerlink.com/link.asp?id=n6501173nh6w8140