Computational Complexity Analysis of Genetic Programming - Initial Results and Future Directions Frank Neumann, Una-May O’Reilly and Markus Wagner The computational complexity analysis of evolutionary algorithms working on binary strings has significantly increased the rigorous understanding on how these types of algorithm work. Similar results on the computational complexity of genetic programming would fill an important theoretic gap. They would significantly increase the theoretical understanding on how and why genetic programming algo- rithms work and indicate, in a rigorous manner, how design choices of algorithm components impact its success. We summarize initial computational complexity results for simple tree-based genetic programming and point out directions for future research.