Autori: Gabriel Istrate

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

Rezumat:

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

URL: http://doi.ieeecomputersociety.org/10.1109/CCC.2000.856740