Generalized satisfiability problems: minimal elements and phase transitions

✍ Scribed by Nadia Creignou; Hervé Daudé

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 263 KB
• Volume: 302
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00890-3

✦ Synopsis

We develop a probabilistic model on the generalized satisÿability problems deÿned by Schaefer (in: Proceedings of the 10th STOC, San Diego, CA, USA, Association for Computing Machinery, New York, 1978, pp. 216 -226) for which the arity of the constraints is ÿxed in order to study the associated phase transition. We establish new results on minimal elements associated with such generalized satisÿability problems. These results are the keys of the exploration we conduct on the location and on the nature of the phase transition for generalized satisÿability. We ÿrst prove that the phase transition occurs at the same scale for every reasonable problem and we provide lower and upper bounds for the associated critical ratio. Our framework allows one to get these bounds in a uniform way, in particular, we obtain a lower bound proportional to the number of variables for k-SAT without analyzing any algorithm. Finally, we reveal the seed of coarseness for the phase transition of generalized satisÿability: 2-XOR-SAT.