# Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions

arXiv: https://arxiv.org/abs/2606.15923 · HTML: https://mlsanity.com/paper/2606.15923/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 40 references that are in the map.
- First posted on arXiv 14 Jun 2026.

## Builds on (most cited first, 5 of 5)

- [Standard Steady State Genetic Algorithms Can Hillclimb Faster than Mutation-only Evolutionary Algorithms](https://mlsanity.com/paper/1708.01571/) (2017)
- [Computational Complexity Analysis of Genetic Programming](https://mlsanity.com/paper/1811.04465/) (2018)
- [Evolving Boolean Functions with Conjunctions and Disjunctions via Genetic Programming](https://mlsanity.com/paper/1903.11936/) (2019)
- [TinyverseGP: Towards a Modular Cross-domain Benchmarking Framework for Genetic Programming](https://mlsanity.com/paper/2504.10253/) (2025)
- [(1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error](https://mlsanity.com/paper/2303.07455/) (2023)

## Abstract (arXiv)

Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Programming as it uses a graph-based representation of programs. This paper presents a first runtime analysis of CGP in evolving Boolean functions using complete training sets. We prove an asymptotic bound O(n D5) for the expected number of fitness evaluations of CGP to construct a conjunction of n inputs using at most D ≥ n-1 binary gates, a minimal function set, and even with a strict survival selection. When the non-strict selection is used, the bound is improved to O(n D4). Our analysis reveals interesting characteristics of CGP induced search, which have been only observed empirically. In particular, enabling the acceptance of equally good solutions, including those with connected gates non-contributing to fitness, can lead to a speedup, and consequently a better asymptotic time bound. In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction. Experiments evolving conjunctions complement our theoretical findings. The use of incomplete training sets is found to further reduce the average number of fitness evaluations while maintaining a good level of generalisation.