# (1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 37 references that are in the map.
- First posted on arXiv 13 Mar 2023.

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

- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [On the Benefits of Populations on the Exploitation Speed of Standard Steady-State Genetic Algorithms](https://mlsanity.com/paper/1903.10976/) (2019)
- [Theoretical Analysis of Stochastic Search Algorithms](https://mlsanity.com/paper/1709.00890/) (2017)
- [Computational Complexity Analysis of Genetic Programming](https://mlsanity.com/paper/1811.04465/) (2018)
- [On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials is Best](https://mlsanity.com/paper/2103.10394/) (2021)
- [Evolving Boolean Functions with Conjunctions and Disjunctions via Genetic Programming](https://mlsanity.com/paper/1903.11936/) (2019)
- [Classification of EEG Signals using Genetic Programming for Feature Construction](https://mlsanity.com/paper/1906.04403/) (2019)

## Built on by (most cited first, 1 of 1)

- [Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions](https://mlsanity.com/paper/2606.15923/) (2026)

## Abstract (arXiv)

Recently it has been proven that simple GP systems can efficiently evolve a conjunction of n variables if they are equipped with the minimal required components. In this paper, we make a considerable step forward by analysing the behaviour and performance of a GP system for evolving a Boolean conjunction or disjunction of n variables using a complete function set that allows the expression of any Boolean function of up to n variables. First we rigorously prove that a GP system using the complete truth table to evaluate the program quality, and equipped with both the AND and OR operators and positive literals, evolves the exact target function in O(ℓ n log2 n) iterations in expectation, where ℓ ≥ n is a limit on the size of any accepted tree. Additionally, we show that when a polynomial sample of possible inputs is used to evaluate the solution quality, conjunctions or disjunctions with any polynomially small generalisation error can be evolved with probability 1 - O(log2(n)/n). The latter result also holds if GP uses AND, OR and positive and negated literals, thus has the power to express any Boolean function of n distinct variables. To prove our results we introduce a super-multiplicative drift theorem that gives significantly stronger runtime bounds when the expected progress is only slightly super-linear in the distance from the optimum.