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