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

Computational Complexity and Phase Transitions

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe

Autori: Gabriel Istrate

Editorial: Proceedings of the 15th I.E.E.E. Conference on Computational Complexity, p.104-115, 2000.


Cheeseman, Kanefsky and Taylor (IJCAI’91) have experimentally shown that the „hardest” (in an average-case sense) instances of combinatorial problems appear at phase transitions. They also conjectured that it is the presence/absence of a phase transition that distinguishes NP-complete problems from those having a polynomial time algorithm. Their conjecture is, of course, naive (there are well-known tractable problems with a phase transition), but whether there exists any connection between worst-case complexity and the existence of a phase transition is an interesting issue. In this paper I study the existence of sharp thresholds for the class of generalized satisfiability problems introduced by Schaefer (STOC’78).
Specifically, I investigate this problem for a particular class of constraints, called clausal constraints and obtain a complete characterization of such problems that have a sharp threshold. The major interest of the result lies in the fact that problems lacking a phase transition can be predicted
with probability 1-o(1) outside the critical region, and lower bounded by a constant inside it by a single, „trivial” satisfiability procedure.
Thus, in this case the lack of a phase transition PROVABLY has algorithmic implications

Cuvinte cheie: phase transitions in combinatorial problems, satisfiability, sharp thresholds