  Understanding the evolution of complexity is an important topic in a wide
variety of academic fields. Implications of better understanding complexity
include increased knowledge of major evolutionary transitions and the
properties of living and technological systems. Genotype-phenotype (G-P) maps
are fundamental to evolution, and biologically-oriented G-P maps have been
shown to have interesting and often-universal properties that enable evolution
by following phenotype-preserving walks in genotype space. Here we use a
digital logic gate circuit G-P map where genotypes are represented by circuits
and phenotypes by the functions that the circuits compute. We compare two
mathematical definitions of circuit and phenotype complexity and show how these
definitions relate to other well-known properties of evolution such as
redundancy, robustness, and evolvability. Using both Cartesian and Linear
genetic programming implementations, we demonstrate that the logic gate circuit
shares many universal properties of biologically derived G-P maps, with the
exception of the relationship between one method of computing phenotypic
evolvability, robustness, and complexity. Due to the inherent structure of the
G-P map, including the predominance of rare phenotypes, large interconnected
neutral networks, and the high mutational load of low robustness, complex
phenotypes are difficult to discover using evolution. We suggest, based on this
evidence, that evolving complexity is hard and we discuss computational
strategies for genetic-programming-based evolution to successfully find
genotypes that map to complex phenotypes in the search space.
