Satisfiability and Evolution

We show that, if truth assignments on n variables reproduce through recombination so that satisfaction of a particular Boolean function confers a small evolutionary advantage, then a polynomially large population over polynomially many generations (polynomial in n and the inverse of the initial satisfaction probability) will end up almost certainly consisting exclusively of satisfying truth assignments. We argue that this theorem sheds light on the problem of the evolution of complex adaptations.

Authors

• Adi Livnat
• Christos H. Papadimitriou
• Aviad Rubinstein
• Gregory Valiant
• Andrew Wan

Keywords

• Sociology
• Statistics
• Boolean functions
• Genetics
• Educational institutions
• Couplings
• Standards
• Almost Surely
• Boolean Function
• Population Size
• Allele Frequency
• Heat Shock
• Quantitative Trait Loci
• Linkage Disequilibrium
• Population Genetic
• Linear Coefficient
• Genotype Frequencies
• Sexual Reproduction
• Product Distribution
• Genotype Distribution
• Fourier Analysis
• Fitness Landscape
• Fourier Coefficients
• Weak Selection
• Linkage Equilibrium
• Percentage Of Flies
• evolution
• algorithms