Inscriere cercetatori

Premii Ad Astra

premii Ad Astra

Asociația Ad Astra a anunțat câștigătorii Premiilor Ad Astra 2022: Proiectul și-a propus identificarea și popularizarea modelelor de succes, a rezultatelor excepționale ale cercetătorilor români din țară și din afara ei.

Asociatia Ad Astra a cercetatorilor romani lanseaza BAZA DE DATE A CERCETATORILOR ROMANI DIN DIASPORA. Scopul acestei baze de date este aceea de a stimula colaborarea dintre cercetatorii romani de peste hotare dar si cu cercetatorii din Romania. Cercetatorii care doresc sa fie nominalizati in aceasta baza de date sunt rugati sa trimita un email la

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

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în revistã ştiinţificã

Autori: Gabriel Istrate, Stephan Boettcher and Allon Percus

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


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

Cuvinte cheie: phase transitions in combinatorial problems, proof complexity