Random 2-SAT Solution Components and a Fitness Landscape
Damien Pitman
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.
Full Text: PDF PostScript