Are complex systems hard to evolve?

Evolutionary complexity is measured here by the number of trials/evaluations needed for evolving a logical gate in a nonlinear medium. Behavioral complexity of the gates evolved is characterized in terms of cellular automata behavior. We speculate that hierarchies of behavioral and evolutionary complexities are isomorphic up to some degree, subject to substrate specificity of evolution, and the spectrum of evolution parameters. © 2009 Wiley Periodicals, Inc