On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.

DOI10.1016/S0166-218X(03)00204-XzbMath1074.68025OpenAlexW2037281185MaRDI QIDQ1421490

Wei Li, Ke Xu

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

zbMATH Keywords

SATConstraint satisfactionPhase transitionSimilarity degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Many hard examples in exact phase transitions

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