Super Solutions of Random Instances of Satisfiability

DOI10.1007/978-3-319-19647-3_29zbMath1356.68112OpenAlexW2407566837MaRDI QIDQ3452579

Yong Gao, Peng Zhang

Publication date: 12 November 2015

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19647-3_29

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)

Cites Work

• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Many hard examples in exact phase transitions
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Frozen development in graph coloring
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Super Solutions of Random Instances of Satisfiability