On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas

DOI10.1137/090749323zbMath1235.68113arXiv0902.2012OpenAlexW2038932251MaRDI QIDQ3094942

Abraham D. Flaxman, Dan Vilenchik

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0902.2012

zbMATH Keywords

phase transitionrandom \(k\)-SAT

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)

This page was built for publication: On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas