A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming

DOI10.1016/j.tcs.2016.04.041zbMath1356.68113OpenAlexW2416495215MaRDI QIDQ507445

Yong Gao, Peng Zhang

Publication date: 6 February 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.041

zbMATH Keywords

probabilistic methodsatisfiabilityconstraint satisfactionthreshold phenomenarandom instancesgeneralized solution conceptssuper solutions

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)

Related Items (2)

On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT ⋮ Super solutions of random \((3 + p)\)-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• The b-chromatic number of a graph
• The \(b\)-chromatic index of graphs
• Many hard examples in exact phase transitions
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• An algorithmic approach to the Lovász local lemma. I
• On Syntactic versus Computational Views of Approximability
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Frozen development in graph coloring

This page was built for publication: A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming