This talk will begin with an gentle introduction to artificial evolution, then explore the interactions between evolvability, complexity and statistics. Artificial evolution has been used to evolve the GE jet engines on the Boeing 777 and to evolve schedules for operating manufacturing lines at Volvo, GM and John Deere--in both cases with performance superior to human efforts. So it is reasonable to ask, what cannot be done via artificial evolution?
Complexity theory tells us that there are problems (i.e. the class NP) that we do not know how to solve deterministically in polynomial time, yet these same problems can be solved by nondeterministic Turing Machines. Limits on the ability of computers to solve NP problems must also limit the capabilities of artificial evolutionary systems.
The connection between "evolvability" and "complexity" however is much deeper. MAXSAT is a keystone problem in the class NP. It turns out that when the MAXSAT representation is viewed as an "artificial chromosome" it is possible to exactly compute the nonlinear interaction between alleles in the corresponding fitness associated with their phenotypic expression. This makes it possible to exactly compute summary statistics (mean, variance, skew and kurtosis) over any subset of interacting alleles. The talk will explore what cannot be done via artificial evolution (and perhaps cannot be done by natural evolution) given what we know about MAXSAT and complexity.