Evolvability∗Leslie G. ValiantSchool of Engineering and Applied SciencesHarvard [email protected] organisms function according to complex mechanisms that operate in different waysdepending on conditions. Evolutionary theory suggests that such mechanisms evolved throughrandom variation guided by selection. However, there has existed no theory that would explainquantitatively which mechanisms can so evolve in realistic population sizes within realistic timeperiods, and which are too complex. In this paper we suggest such a theory. Evolution istreated as a form of computational learning from examples in which the course of learning isinfluenced only by the fitness of the hypotheses on the examples, and not otherwise by thespecific examples. We formulate a notion of evolvability that quantifies the evolvability ofdifferent classes of functions. It is shown that in any one phase of evolution where selection isfor one beneficial behavior, monotone Boolean conjunctions and disjunctions are demonstrablyevolvable over the uniform distribution, while Boolean parity functions are demonstrably not.The framework also allows a wider range of issues in evolution to be quantified. We suggestthat the overall mechanism that underlies biological evolution is evolvable target pursuit, whichconsists of a series of evolutionary stages, each one pursuing an evolvable target in our technicalsense, each target being rendered evolvable by the serendipitous combination of the environmentand the outcome of previous evolutionary stages.1 IntroductionWe address the problem of quantifying how complex mechanisms, such as those found in living cells,can evolve into existence without any need for unlikely events to occur. If evolution merely performeda random search it would require exponential time, much too long to explain the complexity ofexisting biological structures. Darwin suggested selection as the critical controlling principle beyondrandom variation. He also observed that the supposition that the eye could evolve would be “ · · ·absurd in the highest possible degree” were it not for the fact that eyes “vary ever so slightly” andmight therefore evolve over time by selection [5]. In other words, a necessary condition for evolutionto a specific target is the existence of an evolutionary path towards it consisting of small steps.But what are the conditions that hold in biology that are sufficient for such paths to be taken asroutinely and efficiently as they apparently are?This paper describes a quantitative theory of the possibilities and limitations of what selectioncan achieve in speeding up the process of acquiring complex mechanisms beyond mere exhaustive∗This work was supported by grants NSF-CCR-03-10882, NSF-CCF-04-32037 and NSF-CCF-04-27129. Prelim-inary versions of this paper appeared as Electronic Colloquium on Computational Complexity Report TR06-120(2006) and in Proc. 32nd International Symposium on Mathematical Foundations of Computer Science, LNCS Vol4708 (2007) Springer-Verlag, 22-43.1search. In particular, we show that, in a defined quantitative sense, selection for a given beneficialbehavior can provably support the evolution of certain specific classes of mechanisms, and provablynot support that of certain other classes.We approach this problem by viewing mechanisms from the viewpoint of the mathematicalfunctions they realize. In particular the subject matter of the field of computational learning theory[3, 16, 17, 22, 25] can be viewed as that of delineating limits on the complexity of functions that canbe acquired with feasible resources without an explicit designer or programmer. A primary instancestudied there is the acquisition of a recognition algorithm for a function given just p ositive andnegative examples of it. The quantitative study of computational learning over the last two decadeshas shown that certain classes of recognition mechanisms can indeed be learned in a feasible amountof time, while others encounter apparently intractable computational impediments.Our goal here is to give a quantitative theory of the evolution of mechanisms. What we formalizeis concerned with four basic notions. First, since the biology of cells consists of thousands of proteinsand operates with circuits with complex mechanisms, we seek mechanisms that can evaluate many-argument functions. This permits the behavior of circuits to vary in complex ways depending on theparticular combination of values taken by a large number of input parameters. For example, sucha function may determine the expression level of a protein in terms of the expression levels of allthe other proteins. Second, any particular many-argument function has a measure of performancethat is determined by the values of the function on inputs from a probability distribution over theconditions that arise. By applying the function to a variety of conditions, each one correspondingto an experience, the organism will enjoy a cumulative expected benefit that is determined bythis performance. Third, for any function only a limited number of variants can be explored pergeneration, whether through mutations or recombination, since the organisms that can exist at anytime have a limited population. Fourth, there is the requirement that mechanisms with significantimprovements in performance evolve in a limited number of generations.We show that our notion of evolvability is a restricted case of PAC learnability. This offers aunifying framework for the fields of evolution and cognition. The behavior of a biological organismis clearly affected both by the results of evolution and those of learning by the individual. Distin-guishing between the effects of nature and nurture on behavior has proved problematic, and it willperhaps help to have a unifying viewpoint on them.While evolvability as we define it is a form of learnability, it is a constrained form. In PAClearning [25], an update to a hypothesis may depend arbitrarily, as permitted by polynomial timecomputation, on the particular examples presented, on the values computed on them by the hy-pothesis, and on the values of the functions to be learned on those examples. In the more restrictedStatistical Query (SQ) model of Kearns [15] the updates can depend only on the result of statisticalqueries on the distribution of examples. However, these queries can ask about the percentage ofexamples that have certain properties b eside being positive or