Random 2-SAT Solution Components and a Fitness Landscape

Abstract : We describe a limiting distribution for the number of connected components in the subgraph of the discrete cube induced by the satisfying assignments to a random 2-SAT formula. We show that, for the probability range where formulas are likely to be satisfied, the random number of components converges weakly (in the number of variables) to a distribution determined by a Poisson random variable. The number of satisfying assignments or solutions is known to grow exponentially in the number of variables. Thus, our result implies that exponentially many solutions are organized into a stochastically bounded number of components. We also describe an application to biological evolution; in particular, to a type of fitness landscape where satisfying assignments represent viable genotypes and connectivity of genotypes is limited by single site mutations. The biological result is that, with probability approaching 1, each viable genotype is connected by single site mutations to an exponential number of other viable genotypes while the number of viable clusters is finite.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 2 (2), pp.45--62
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990478
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:39:03
Dernière modification le : jeudi 7 septembre 2017 - 01:03:36
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:22:46

Fichier

1024-6321-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990478, version 1

Collections

Citation

Damien Pitman. Random 2-SAT Solution Components and a Fitness Landscape. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 2 (2), pp.45--62. 〈hal-00990478〉

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

256