A general model and thresholds for random constraint satisfaction problems
From MaRDI portal
Publication:359981
DOI10.1016/j.artint.2012.08.003zbMath1270.68267MaRDI QIDQ359981
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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Fractional Edge Cover Number of Model RB, Phase Transition for Maximum Not-All-Equal Satisfiability, Bounding the scaling window of random constraint satisfaction problems, Performances of pure random walk algorithms on constraint satisfaction problems with growing domains, On the phase transitions of \((k, q)\)-SAT, The scaling window of the model \(d\)-\(k\)-CSP, Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length, Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP, Large hypertree width for sparse random hypergraphs
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
