Gabriel Istrate. Computational Complexity and Phase Transitions. In Proceedings of the 15th I. E. E. E. Conference on Computational Complexity, pp. 104115. 2000.
Abstract:
Cheeseman, Kanefsky and Taylor (IJCAI'91) have experimentally shown that the "hardest" (in an averagecase sense) instances of combinatorial problems appear at phase transitions. They also conjectured that it is the presence/absence of a phase transition that distinguishes NPcomplete problems from those having a polynomial time algorithm. Their conjecture is, of course, naive (there are wellknown tractable problems with a phase transition), but whether there exists any connection between worstcase 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 1o(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
Keywords:
phase transitions in combinatorial problems, satisfiability, sharp thresholds
URL:
http://doi.ieeecomputersociety.org/10.1109/CCC.2000.856740
Posted by
Gabriel Istrate
Back
