Scopul nostru este sprijinirea şi promovarea cercetării ştiinţifice şi facilitarea comunicării între cercetătorii români din întreaga lume.
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