A sharp threshold for a random constraint satisfaction problem
From MaRDI portal
Publication:1877674
DOI10.1016/j.disc.2004.05.002zbMath1121.68407MaRDI QIDQ1877674
Publication date: 19 August 2004
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2004.05.002
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
06E30: Boolean functions
Related Items
A general model and thresholds for random constraint satisfaction problems, On the phase transitions of \((k, q)\)-SAT, On the phase transitions of random \(k\)-constraint satisfaction problems, 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, Many hard examples in exact phase transitions, Locally consistent constraint satisfaction problems, Sharp thresholds for constraint satisfaction problems and homomorphisms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A threshold for unsatisfiability
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Generalized satisfiability problems: Minimal elements and phase transitions.
- Random 2-SAT and unsatisfiability
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- The threshold for random k-SAT is 2 k (ln 2 - O(k))
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Sharp thresholds of graph properties, and the $k$-sat problem
- On the 2-colorability of random hypergraphs
- Bounding the unsatisfiability threshold of random 3-SAT
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Random 2-SAT: Results and problems