Expected number of locally maximal solutions for random Boolean CSPs

Expected number of locally maximal solutions for random Boolean CSPs

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 se...

Full description

Bibliographic Details
Main Authors: Nadia Creignou, Hervé Daudé, Olivier Dubois
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2007-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
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]
Online Access:https://dmtcs.episciences.org/3539/pdf

Internet

https://dmtcs.episciences.org/3539/pdf

Similar Items