Computational Complexity, Genetic Programming, and Implications

Created by W.Langdon from gp-bibliography.bib Revision:1.4216

  author =       "Bart Rylander and Terry Soule and James Foster",
  title =        "Computational Complexity, Genetic Programming, and
  booktitle =    "Genetic Programming, Proceedings of EuroGP'2001",
  year =         "2001",
  editor =       "Julian F. Miller and Marco Tomassini and 
                 Pier Luca Lanzi and Conor Ryan and Andrea G. B. Tettamanzi and 
                 William B. Langdon",
  volume =       "2038",
  series =       "LNCS",
  pages =        "348--360",
  address =      "Lake Como, Italy",
  publisher_address = "Berlin",
  month =        "18-20 " # apr,
  organisation = "EvoNET",
  publisher =    "Springer-Verlag",
  keywords =     "genetic algorithms, genetic programming, Computational
                 Complexity, Quantum Computing: Poster",
  ISBN =         "3-540-41899-7",
  URL =          "",
  URL =          "",
  DOI =          "doi:10.1007/3-540-45355-5_28",
  size =         "13 pages",
  abstract =     "Recent theory work has shown that a Genetic Program
                 (GP) used to produce programs may have output that is
                 bounded above by the GP itself [l]. This paper presents
                 proofs that show that 1) a program that is the output
                 of a GP or any inductive process has complexity that
                 can be bounded by the Kolmogorov complexity of the
                 originating program; 2) this result does not hold if
                 the random number generator used in the evolution is a
                 true random source; and 3) an optimization problem
                 being solved with a GP will have a complexity that can
                 be bounded below by the growth rate of the minimum
                 length problem representation used for the
                 implementation. These results are then used to provide
                 guidance for GP implementation.",
  notes =        "EuroGP'2001, part of \cite{miller:2001:gp}",

Genetic Programming entries for Bart I Rylander Terence Soule James A Foster