Solution space coupling in the random K-satisfiability problem

DOI10.1088/0253-6102/60/3/18MaRDI QIDQ5407006zbMATH OpenOpenAlexFDO

Authors Ying Zeng, Haijun Zhou

Publication date 4 April 2014

Published in Communications in Theoretical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1088/0253-6102/60/3/18

zbMATH Keywords

belief propagationclustering transitionconstraint satisfactionsolution space

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Recommendations

• Solution clustering in random satisfiability
• On the solution-space geometry of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• Threshold values of random K‐SAT from the cavity method
• Pairs of SAT-assignments in random Boolean formulæ

This page was built for publication: Solution space coupling in the random \(K\)-satisfiability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5407006)