Models for Random Constraint Satisfaction Problems

DOI10.1137/S0097539700368667zbMath1029.68118MaRDI QIDQ4706240

No author found.

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

sharp threshold; threshold; constraint satisfaction problems; random models

Mathematics Subject Classification ID

68R99: Discrete mathematics in relation to computer science

Related Items

Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, Streamlining variational inference for constraint satisfaction problems, Combinatorial sharpness criterion and phase transition classification for random CSPs, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The scaling window of the model \(d\)-\(k\)-CSP, The SAT-UNSAT transition for random constraint satisfaction problems, Random constraint satisfaction: easy generation of hard (satisfiable) instances, When does the giant component bring unsatisfiability?, Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities, Many hard examples in exact phase transitions, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, An algorithm for random signed 3-SAT with intervals, Satisfiability Thresholds beyond k −XORSAT