Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

Gabriel Istrate. Computational Complexity and Phase Transitions. In Proceedings of the 15th I. E. E. E. Conference on Computational Complexity, pp. 104-115. 2000.

Abstract: 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

Keywords: phase transitions in combinatorial problems, satisfiability, sharp thresholds


Posted by Gabriel Istrate


© Ad Astra 2001-2013