The satisfiability threshold for randomly generated binary constraint satisfaction problems
ALAN M. FRIEZE, Michael S. O. Molloy · Random Structures and Algorithms · 2006
Abstract We study two natural models of randomly generated constraint satisfaction problems. We determine how quickly the domain size must grow withnto ensure that these models are robust in the sense that they exhibit a non‐trivial threshold of satisfiability, and we determine the asymptotic order of that threshold. We also provide resolution complexity lower bounds for these models. One of our results immediately yields a theorem regarding homomorphisms between two random graphs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006