  The computational complexity analysis of genetic programming (GP) has been
started recently by analyzing simple (1+1) GP algorithms for the problems ORDER
and MAJORITY. In this paper, we study how taking the complexity as an
additional criteria influences the runtime behavior. We consider
generalizations of ORDER and MAJORITY and present a computational complexity
analysis of (1+1) GP using multi-criteria fitness functions that take into
account the original objective and the complexity of a syntax tree as a
secondary measure. Furthermore, we study the expected time until
population-based multi-objective genetic programming algorithms have computed
the Pareto front when taking the complexity of a syntax tree as an equally
important objective.
