Nadia Creignou ; Hervé Daudé ; Olivier Dubois - Expected number of locally maximal solutions for random Boolean CSPs

dmtcs:3539 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3539
Expected number of locally maximal solutions for random Boolean CSPsArticle

Authors: Nadia Creignou 1; Hervé Daudé 2; Olivier Dubois 3

  • 1 Laboratoire d'informatique Fondamentale de Marseille
  • 2 Laboratoire d'Analyse, Topologie, Probabilités
  • 3 Recherche Opérationnelle

For a large number of random Boolean constraint satisfaction problems, such as random $k$-SAT, we study how the number of locally maximal solutions evolves when constraints are added. We give the exponential order of the expected number of these distinguished solutions and prove it depends on the sensitivity of the allowed constraint functions only. As a by-product we provide a general tool for computing an upper bound of the satisfiability threshold for any problem of a large class of random Boolean CSPs.


Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Section: Proceedings
Published on: January 1, 2007
Imported on: May 10, 2017
Keywords: Threshold,Phase transition,Satisfiability,Random structures,Constraint satisfaction problems,Boolean functions,Sensitivity,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

3 Documents citing this article

Consultation statistics

This page has been seen 208 times.
This article's PDF has been downloaded 195 times.