Premium
The satisfiability threshold for randomly generated binary constraint satisfaction problems
Author(s) -
Frieze Alan,
Molloy Michael
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20118
Subject(s) - constraint satisfaction problem , satisfiability , homomorphism , constraint (computer aided design) , constraint satisfaction , discrete mathematics , binary number , mathematics , random graph , computer science , combinatorics , statistics , arithmetic , graph , probabilistic logic , geometry
We study two natural models of randomly generated constraint satisfaction problems. We determine how quickly the domain size must grow with n to 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