Name
Abstract | ||
|---|---|---|
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 Daudé [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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.dam.2005.05.010 | Discrete Applied Mathematics |
Keywords | Field | DocType |
random constraint satisfaction problems,sharp thresholds,random boolean constraint satisfaction,boolean case,random generalized satisfiability problem,phase transition classification,random constraint satisfaction problem,restricted case,random csps,threshold property,generalized satisfiability problem,phase transition,sharp threshold,classification result,probabilistic model,constraint satisfaction problem,satisfiability | Discrete mathematics,Combinatorics,Theory of computing,Satisfiability,Boolean satisfiability problem,Constraint satisfaction problem,Statistical model,Mathematics | Journal |
Volume | Issue | ISSN |
153 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.43 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gabriel Istrate | 1 | 99 | 24.96 |