A general model and thresholds for random constraint satisfaction problems

DOI10.1016/j.artint.2012.08.003zbMath1270.68267OpenAlexW2030163620MaRDI QIDQ359981

Yun Fan, Ke Xu, Jing Shen

Publication date: 23 August 2013

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0004370212001038

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ Fractional Edge Cover Number of Model RB ⋮ Phase Transition for Maximum Not-All-Equal Satisfiability ⋮ On the phase transitions of \((k, q)\)-SAT ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ Large hypertree width for sparse random hypergraphs ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• A probabilistic analysis of randomly generated binary constraint satisfaction problems.
• Generalized satisfiability problems: Minimal elements and phase transitions.
• A sharp threshold for a random constraint satisfaction problem
• On the satisfiability threshold of formulas with three literals per clause
• Many hard examples in exact phase transitions
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• An empirical study of phase transitions in binary constraint satisfaction problems
• Locating the phase transition in binary constraint satisfaction problems
• Two Hardness Results on Feedback Vertex Sets
• Many hard examples for resolution
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Models and thresholds for random constraint satisfaction problems
• Sharp thresholds of graph properties, and the $k$-sat problem
• Short proofs are narrow—resolution made simple
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• A Note on Treewidth in Random Graphs
• Probability and Computing
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Principles and Practice of Constraint Programming – CP 2004
• Random constraint satisfaction: Flaws and structure
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems

This page was built for publication: A general model and thresholds for random constraint satisfaction problems