Expected number of locally maximal solutions for random Boolean CSPs

MaRDI QIDQ3576757zbMATH OpenFDO

Authors Nadia Creignou, Hervé Daudé, Olivier Dubois

Publication date 2 August 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAH0108/0.html

zbMATH Keywords

sensitivitythresholdphase transitionconstraint satisfaction problemssatisfiabilityBoolean functionsrandom structures

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Computer aspects of numerical algorithms (65Y99)

Recommendations

• Super solutions of random instances of satisfiability
• Threshold properties of random Boolean constraint satisfaction problems
• A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
• Random constraint satisfaction: A more accurate picture
• On the concentration of the number of solutions of random satisfiability formulas

Cited in

(2)

• New Results on the Phase Transition for Random Quantified Boolean Formulas
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs

This page was built for publication: Expected number of locally maximal solutions for random Boolean CSPs

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