Expected number of locally maximal solutions for random Boolean CSPs

zbMATH Open1192.68951MaRDI QIDQ3576757FDOQ3576757

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

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

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)

Cited In (2)

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

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)