Conclusions

• Size and shape of search space
• Experimental evidence, tree based GP
• Proof linear
• Chance of long random solution $=2^{- \vert\mbox{test set}\vert}$ (symmetric)

• Proof tree
• Number of solutions grows exponentially with size

ftp cs.ucl.ac.uk/genetic/gp-code ntrees.cc rand_tree.cc