We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy [Models for random constraint satisfaction problems, in: Proceedings of the 32nd ACM Symposium on Theory of Computing, 2002]. We give a sufficient condition for the existence of a sharp threshold. In the boolean case, it gives an independent proof for the more difficult half of a classification result conjectured by Creignou and Daude [Generalized satisfiability problems: minimal elements and phase transitions. Theor. Comput. Sci. 302(1-3) (2003) 417-430], proved in a restricted case by the same authors [Combinatorial sharpness criterion and phase transition classification for random CSPs, Inform. Comput. 190(2) (2004) 220-238], and established by them [Coarse and sharp thresholds for random generalized satisfiability problems, in: M. Drmota, P. Flajolet, D. Gardy, B. Gittenberger (Eds.), Mathematics and Computer Science III: Algorithms, Trees, Combinatorics and Probabilities, Birkhauser, Basel, September 2004, pp. 507-517] while this paper was in the refereeing process. (c) 2005 Elsevier B.V. All rights reserved.
展开▼
