Models and thresholds for random constraint satisfaction problems

DOI10.1145/509907.509941zbMath1192.68652OpenAlexW2045071513MaRDI QIDQ3579225

No author found.

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.509941

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (16)

Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ List coloring triangle-free hypergraphs ⋮ An algorithm for random signed 3-SAT with intervals ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Generalized satisfiability problems: Minimal elements and phase transitions. ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Hunting for sharp thresholds ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ The satisfiability threshold for randomly generated binary constraint satisfaction problems ⋮ On Random Ordering Constraints ⋮ Acyclic edge colourings of graphs with large girth ⋮ Geometric properties of satisfying assignments of random ε-1-in-kSAT ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story ⋮ Threshold properties of random Boolean constraint satisfaction problems ⋮ Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story ⋮ Spines of random constraint satisfaction problems: definition and connection with computational complexity

This page was built for publication: Models and thresholds for random constraint satisfaction problems