Models and thresholds for random constraint satisfaction problems

DOI10.1145/509907.509941zbMath1192.68652MaRDI 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

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

Related Items

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