On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
From MaRDI portal
Publication:1421490
DOI10.1016/S0166-218X(03)00204-XzbMath1074.68025OpenAlexW2037281185MaRDI QIDQ1421490
Publication date: 26 January 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00204-x
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A threshold for unsatisfiability
- Exploiting the deep structure of constraint problems
- The SAT phase transition
- An average analysis of backtracking on random constraint satisfaction problems
- An empirical study of phase transitions in binary constraint satisfaction problems
- Locating the phase transition in binary constraint satisfaction problems
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- An Average Time Analysis of Backtracking
- Approximating the unsatisfiability threshold of random formulas
- Determining computational complexity from characteristic ‘phase transitions’
- Random constraint satisfaction: A more accurate picture
- Random constraint satisfaction: Flaws and structure
- Rigorous results for random (\(2+p)\)-SAT