Sharp thresholds for constraint satisfaction problems and homomorphisms |
| |
| Authors: | Hamed Hatami Michael Molloy |
| |
| Institution: | Department of Computer Science, University of Toronto, Toronto, Canada |
| |
| Abstract: | We determine under which conditions certain natural models of random constraint satisfaction problems have sharp thresholds of satisfiability. These models include graph and hypergraph homomorphism, the (d,k,t)‐model, and binary constraint satisfaction problems with domain size three. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
| |
| Keywords: | satisfiability thresholds random graphs random constraint satisfaction problems |
|
|
