Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> 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

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

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013