Satisfiability & Evolution

How does a beneficial trait, one that is determined by the interaction between many genes, become fixed in a population? We consider the interaction between n genes and their evolving genotype frequencies, with reproduction through recombination, as a process on a Boolean function: when the Boolean function is satisfied by an assignment (i.e., a genotype), a small evolutionary advantage is conferred. Our main result shows that for any Boolean function and populations of polynomial size (polynomial in the number of genes and the inverse probability of initial satisfaction), with very high probability every individual in the population will be satisfying after polynomially many generations.  In this talk I will present some details of the proof. This is joint work with Adi Livnat, Christos Papadimitriou, Aviad Rubinstein and Greg Valiant