  Genetic programming (GP) is an evolutionary computation technique to solve
problems in an automated, domain-independent way. Rather than identifying the
optimum of a function as in more traditional evolutionary optimization, the aim
of GP is to evolve computer programs with a given functionality. While many GP
applications have produced human competitive results, the theoretical
understanding of what problem characteristics and algorithm properties allow GP
to be effective is comparatively limited. Compared with traditional
evolutionary algorithms for function optimization, GP applications are further
complicated by two additional factors: the variable-length representation of
candidate programs, and the difficulty of evaluating their quality efficiently.
Such difficulties considerably impact the runtime analysis of GP, where space
complexity also comes into play. As a result, initial complexity analyses of GP
have focused on restricted settings such as the evolution of trees with given
structures or the estimation of solution quality using only a small polynomial
number of input/output examples. However, the first computational complexity
analyses of GP for evolving proper functions with defined input/output behavior
have recently appeared. In this chapter, we present an overview of the state of
the art.
