Paper deep dive
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions
Duc-Cuong Dang, Roman Kalkreuth, Andre Opris
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 6/20/2026, 7:32:36 AM
Summary
This paper provides the first runtime analysis of Cartesian Genetic Programming (CGP) for evolving Boolean functions. The authors prove that for constructing a conjunction of $n$ inputs using at most $D \geq n-1$ binary gates, the expected number of fitness evaluations is $O(nD^5)$ for strict selection and $O(nD^4)$ for non-strict selection. Conversely, they prove that evolving an exclusive disjunction (XOR) requires exponential time. The study highlights that non-strict selection (accepting equally good solutions) leads to a speedup and better asymptotic bounds. The research also explores the impact of incomplete training sets on generalization and performance.
Entities (8)
Relation Signals (4)
Cartesian Genetic Programming → evolves → Boolean Function
confidence 100% · 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...
Cartesian Genetic Programming → hascomplexity → O(nD^5)
confidence 100% · We prove an asymptotic bound O(n D^5) for the expected number of fitness evaluations of CGP to construct a conjunction of n inputs
Cartesian Genetic Programming → hasexponentialtimefor → Exclusive Disjunction
confidence 100% · In contrast to conjunctions, we also prove a negative result which shows that CGP requires exponential time to evolve an exclusive disjunction.
Single Active-Gene Mutation → isusedin → Cartesian Genetic Programming
confidence 100% · We consider the popular single active-gene mutation (SAM) [9] and the minimal function sets.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 D^5)$ for the expected number of fitness evaluations of CGP to construct a conjunction of $n$ inputs using at most $D \geq 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 D^4)$. 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.
Tags
Links
- Source: https://arxiv.org/abs/2606.15923v1
- Canonical: https://arxiv.org/abs/2606.15923v1
Trouble viewing inline? Open PDF directly →
Full Text
67,967 characters extracted from source content.
Expand or collapse full text
Runtime Analysis of Cartesian Genetic Programming in Evolving Boolean Functions Duc-Cuong Dang 1 , Roman Kalkreuth 2 , and Andre Opris 1 1 University of Passau, Passau, Germany 2 RWTH Aachen University, Aachen, Germany Abstract Cartesian Genetic Programming (CGP) is among the practical and popular forms of Genetic Program- ming 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(nD 5 ) 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(nD 4 ). 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. 1 Introduction Genetic Programming (GP) is a search paradigm originally proposed for the automated discovery of computer programs. GP leverages evolutionary search using selection and variation to evolve programs given a specifi- cation, constraints, and input-output examples. Early work by Cramer [4] and Dickmanns et al. [5] applied Genetic Algorithms (GA) to evolve computer programs. However, Koza [17, 18] later introduced a tree-based form of GP to evolve symbolic expressions, commonly implemented as LISP S-expressions at that time, which widely popularised the concept of GP. The traditional form of GP therefore uses tree data structures to model programs, and this is commonly referred to as Tree-based GP (TGP). The leaf nodes represent the inputs of the program and are assigned elements from a terminal set T , which consists of variables or constants. The root and internal nodes compute functions from a function set F , taking the arguments from the outputs of their respective child nodes. After evaluation, the value produced at the root node constitutes the final output of the modeled program. Over time, GP has been extended to incorporate alternative program representations, including linear sequences [32, 31], graph-based structures [33, 26], and rule-based models [34]. In this work, we are interested in Cartesian Genetic Programming (CGP) [25], which is, unlike TGP, a graph- based form of GP. CGP is a well established methodology in logic synthesis and evolvable hardware [40], with many successful applications such as in designing high order combinational circuits [39], complex approximate circuits [41], and cryptographic functions [11]. These successes are believed to be due to the high versatility of the graph-based representation. Learning Boolean functions was also among the motivating applications for the introduction of CGP [26]. However, it remains poorly understood when and why even simple CGP algorithms perform well in this problem domain, and a solid theoretical foundation for CGP in evolving Boolean functions is still missing. 1 arXiv:2606.15923v1 [cs.NE] 14 Jun 2026 Our contribution: Inspired by the work of Mambrini and Oliveto [22] on TGP, we initiate a rigorous analysis of CGP for evolving Boolean functions by analysing the runtime of the (1+1) CGP and the strict variant (1+1) CGP ∗ . We consider the popular single active-gene mutation (SAM) [9] and the minimal function sets. For constructing conjunctions of n variables with D ≥ n− 1 And gates and the complete training set, we obtain expected runtimes of O(nD 4 ) and O(nD 5 ), respectively, using fitness-level arguments and Markov chain analysis. The faster performance of (1+1) CGP over (1+1) CGP ∗ stems from its non strict selection, which accepts equally fit solutions with redundant active gates, a beneficial effect previously observed only empirically [35]. Prior counterpart TGP results [19, 22] make no distinction between strict and non strict selection, and in comparison, CGP is slower but guarantees to only useO(D logD) space. The original CGP [26] was not designed for speeding up TGP, but to offer a more general representation of programs with natural support for Boolean circuit applications. A CGP program in the Boolean domain is a logic circuit. The aim of our paper is not about showing a superior performance, but rather to understand how and when polynomial performance guarantees can be achieved. In contrast to conjunctions, we prove that (1+1) CGP requires exponential time with exponentially high probability, to construct an exclusive disjunction of n inputs out of (1 + d)n≥ D ≥ n− 1 XOR gates for some d < 1 and using the complete training set. Here we apply the negative drift theorem [29]. Experiments on conjunctions support the theory, showing clear gains by using non strict selection. We also conduct experi- ments using incomplete static training sets, and observe that this setting further reduces the number of fitness evaluations required by CGP while maintaining a good level of generalisation. Related work: From the empirical side, several studies have examined search behaviour of CGP, primarly focusing on characteristics such as neutral search [43], redundancy [24], bloat [35] and evolvability in the fitness landscapes induced by logic synthesis problems [43]. Moreover, based on the results of empirical studies, it has been demonstrated and hypothesised that CGP-driven program search benefits from high levels of redundancy, enabled by the use of very large genotypes [24, 35]. This also includes handling neutral fitness landscapes by neutral genetic drift (NGD), which has been shown to help escape local optima [43, 36]. A step forward in understanding the complexity characteristics of CGP induced search in logic synthesis was made by the proposal of the General Boolean Function Suite (GBFS) [14]. This is a diverse benchmark of different types of Boolean functions commonly used to evaluate GP methods. Mambrini and Oliveto [22] were the first to rigorously analyse GP in evolving Boolean functions by consid- ering the same TGP systems as [27, 16] using the minimal function sets. On the complete training set, they showed that the (1+1) TGP and (1+1) TGP ∗ with the single-step (local) mutation constructs a conjunction of n inputs inO(n logn) expected fitness evaluations. On a static incomplete training sampled uniformly at random of s ∈ poly(n) rows, the time bound to fit the training set is reduced to O(logn). Using the negative drift theorem, they also showed that the (1+1) TGP requires exponential time to construct an exclusive disjunction of n variables. Other setting were also considered in their paper, such as constructing exclusive disjunction with incomplete training set, and conjunction with negated input variables. These results were later extended for the algorithms with the multi-step (global) mutation in Lissovoi and Oliveto [19, 20], which added the generalisation ability guarantee for conjunctions on incomplete training sets, along with many other results. Doerr et al. [7, 8] pushed this line of research further by considering the settings of non-minimal function sets, unknown target function size, and introduced a new tool, called the super-multiplicative theorem, for their analysis. For CGP, we are unaware of any theoretical research in learning Boolean functions. The only work on runtime analysis of CGP that we know of is from Kalkreuth and Droschinsky [12] on one function node. Finally, the book chapter [21] summarises the current state-of-the-art theoretical research on GP. 2 Preliminaries We use the asymptotic notation with symbols Ω, O, Θ [1]. The sets of integer and natural numbers are Z and N respectively. For n ∈ N, define [n] : = 1,...,n and [n] 0 : = [n]∪0. The natural logarithm is denoted 2 ln(·) and that of base-2 is log(·). We use H n to denote the n-th harmonic number, i. e. ln(n + 1) < H n : = P n i=1 1 i < 1 + ln(n), thus H n =O(logn). Let Li s (z) := P ∞ i=1 z i i s be the polylogarithm (or Jonqui`ere’s) function for s,z ∈ C, i. e. extended by analytic continuation. Some special cases are Li −2 (z) = P ∞ i=1 i 2 z i = z(1+z) (1−z) 3 for |z| < 1, and Li s (1) = P ∞ i=1 1 i s =: ζ(s) which is known as the Riemann’s Zeta function. Note that ζ(2) = π 2 /6 and ζ(4) = π 4 /90. The logic And, Or and exclusive Or are denoted ∧, ∨ and ⊕ respectively. The uniform distribution over a set A is denoted Unif(A) and the geometric distribution with parameter p∈ [0, 1] is denoted Geom(p). For two random variables X,Y , X ⪰ Y means that X stochastically dominates Y , that is, for any a∈ R it holds Pr (X ≤ a)≤ Pr (Y ≤ a). 2.1 Cartesian Genetic Programming CGP is capable of modelling programs with N in inputs and N out outputs, and uses N func (internal) function nodes. The functions that can be used to compute the output of those nodes are defined in a lookup table of K entries indexed from 0 to K − 1. The function specified in each entry has an arity of at most k. A (valid) program for such a CGP is then represented by a directed acyclic graph G = (V,E), referred to as the phenotype, which defines how the outputs are computed by composing functions of the lookup table and using the respective inputs. The inputs and the lookup table model the same concepts as the terminal set T and the function set F in Tree-based GP, thus any TGP program always has an equivalent CGP program. The original form of CGP [26] was proposed to arrange the function nodes on a grid-like structure similar to an FPGA circuit. However, we consider the modern (simplified) approach in which the nodes are arranged in a single line, thus V can be indexed from 0 to N− 1 where N := N in +N func +N out or simply V = [N− 1] 0 , i. e. starting with the input nodes N in , then the function nodes N func , and finally the output ones N out . Each input node has no incoming edges (or connections) while each output node has exactly one coming from a non-output node, i. e. with index in [N−N out − 1] 0 . Each function node is labelled with a function of the lookup table and has exactly k incoming edges from nodes of strictly smaller indices, thus from the inputs or from the outputs of the preceding function nodes. These edges represent the sequence of arguments that the function at the node takes, thus there is an ordering among them. If the arity of the corresponding function in the lookup table is smaller k, then only some first edges matter. It is possible for a CGP program to ignore some of the function nodes, which are referred to as inactive (function) nodes. More generally, a non-terminal node of V is called active if there is a path from this specific node to one of the output nodes, otherwise it is called inactive. By this definition, output nodes are always active. The genotype (or the encoding) of G is a vector of N func (k + 1) +N out integers. The sequence is divided into N func +N out blocks indexed from N in to N− 1, and these indices match those nodes in the phenotype that the blocks encode. A block with index i < N in + N func (a so called function block) contains k + 1 integers (or genes), the first, referred to as the function gene, is a number in [K − 1] 0 (pointing to an index in the lookup table) while the rest, referred to as function connection genes, are integers in [i− 1] 0 . Blocks with a larger index than i (output blocks) only contain one integer in [N − N out − 1] 0 , called the output connection gene. Thus the set of all genotypes (all valid CGP programs), denoted by X , is an integer-valued space. Unlike TGP, CGP therefore has a fixed space complexity to store a program as stated in the lemma below. Figure 1 gives an example of a CGP program with its phenotype representation and the corresponding genotype encoding. Lemma 1. Only (N func (k + 1) + N out ) log(1 + maxK,N in + N func ) storage space is required to store a CGP program. Proof. The program is encoded by a vector of N func (k + 1) +N out integers. Each integer is bounded from above by maxK,N in + N func , thus at most log(1 + maxK,N in + N func ) bits are required to encode it. The total number of bits is (N func (k + 1) + N out ) log(1 + maxK,N in + N func ). We consider the simplest CGP algorithm the so-called (1+1) CGP (Algorithm 1 for minimisation). Starting from a program initialised uniformly at random, in each iteration a new offspring program y is generated by mutating the current one. The offspring will replace the parent only if it has better or equally good fitness. Here 3 lookup table indexsymbolfunc. 0∧And 1∨Or 2 ↓Nor phenotype x 1 0 x 2 1 x 3 2 ∧ 3 ↓ 4 ∨ 5 ↓ 6 ∧ 7 o 1 8 genotype 0 0 1 3 2 3 2 4 1 4 3 5 2 0 4 6 0 5 1 7 7 8 equivalent circuit x 1 x 2 x 3 3 4 5 7 o 1 Figure 1: Example of a CGP program that models a Boolean function. Node 6 is a so-called inactive node since no path touching this node leads to the output. f (x) is referred to as the fitness of a program x which is problem-dependent and assumed given. By convention in runtime analysis, we let the algorithm run infinitely then estimate the expected time to reach some target state. Like TGP [22], we also refer to the variant of the (1+1) CGP where strict comparison is used instead in Line 4 as the (1+1) CGP ∗ . Mutations in CGP can alter any gene (component) of the genotype (vector) to a new value uniformly at random while respecting the constraint on their range, this is done with the help of the procedure NewValue which is summarised in Algorithm 2. When enforcing the change of the gene value is not possible, for example if only one function is specified in the lookup table then the function genes are fixed to zero and cannot be mutated, the old value is returned instead. The original paper [23] proposed point mutation operators in which a fixed or random number of genes (mutation points) are chosen uniformly at random for alternation. Nowadays, the so-called single active-gene mutation (SAM) [9] is more popular and is our focus. SAM is parameter-free and is described in Algorithm 3. It repeatedly modifies genes chosen uniformly at random until an active node is modified. The detection of active nodes can be done during the program evaluation, so we assume that there is a function IsActive that can tell whether a given gene belongs to an active node or not in an evaluated program. 2.2 Learning Boolean Functions with GP Learning Boolean functions or, more generally, logic circuits with heuristic methods is part of the wider field of logic synthesis [10]. In this section, we describe how the learning is evaluated for any GP. The problem of learning a Boolean function g : Bool n → Bool on n inputs where Bool :=True, False is to compose a program/circuit a set of elementary logic gates to exactly match or to approximates g using a set S of input-output examples of g referred to as the training set. To accommodate the construction of S by random sampling, we rather consider S as a multi-set, each of its elements is called a row which consists of a pair of example input assignment α∈ Bool n and the desired output g(α)∈ Bool. Formally, the set of input variables is T :=x i | i∈ [n] and coincides with the GP terminal set. Then each α : T → Bool is a mapping of every input to a Boolean value. Like g, a given candidate program y is also a function x 1 ,...,x n 7→ y(x 1 ,...,x n ) Algorithm 1: The (1+1)-CGP on the space X of programs. 1 x∼ Unif(X ) 2 for iter := 1→∞ do 3y := mut(x) 4if f (y)≤ f (x) then x := y 4 Algorithm 2: NewValue(x,i). 1 b :=⌊i/(k + 1)⌋// block index 2 j := i mod (k + 1)// index inside a block 3 if i < N func (k + 1) then 4if j = 0 then S := [K− 1] 0 // valid functions 5else S := [N in + b− 1] 0 // valid input connections 6 else 7S := [N in + N func − 1] 0 // valid output connnections 8 if |S\x[i]|≥ 1 then 9S := S\x[i]// avoid the old value if possible 10 v ∼ Unif(S) 11 return v Algorithm 3: MutationSAM(x). 1 Copy x to y 2 active := false 3 while ¬active do 4i∼ Unif([N func (k + 1) + N out − 1] 0 ) 5y[i] := NewValue(y, i) 6active := IsActive(x, i)∧ (y[i]̸= x[i]) 7 return y on the inputs. To calculated the fitness of y, the number of mismatched outputs of y on S is counted, that is, f (y) :=|(α,g(α))∈ S | y(α(x 1 ),...,α(x n ))̸= g(α(x 1 ),...,α(x n ))|. Thus the smaller f (y) is the closer y is to fully fit the training set S. In the so-called synthesis with the complete training set, the complete specification of g is available and is used to evaluate candidate programs, that is, S = K g where K g := (α,g(α(x 1 ),...,α(x n ))) α∈bool n is the complete truth table of g. Since the truth table grows exponentially in n, i. e. |K g | = 2 n , in practice to reduce the computational time of each fitness evaluation for large n, only a fraction of K g is sampled and used as training set S. This is referred to as synthesis with an incomplete training set. We assume that S is sampled once and remains unchanged during evolution, i. e. S is called a static training set. We only consider the complete training set in our theoretical analysis, the reason is discussed in the last section of the paper. However, in experiments, incomplete training sets are considered. Similarly to [7, 22], we define the generalisation error ε g (y) of a program y in modelling a target function g as the probabil- ity that y returns a mismatched output of a row selected uniformly at random from K g , i. e. ε g (y) := Pr (y(α(x 1 ),...,α(x n ))̸= g(α(x 1 ),...,α(x n ))) where α ∼ Unif(Bool n ). The generalisation ability of y is the complement of its generalisation error, i. e. G g (y) := 1− ε g (y). Thus y fully meets the specification of g if and only if G g (y) = 1. A value of G g (y) close 1 means that y generalises g well while a value close to 1/2 means that it is only as good as a random guess. A program y with G g (y) close to 0 can be turned to ̄y with G g ( ̄y) close to 1, thus y and ̄y are equally informative of g. The exact computation of G g (y) is of course expensive, however it can be approximated by considering a validation set (also called test set ) S ′ which is sufficiently large and is created independently from S by sampling the rows of K g uniformly at random with replacement. The fitness of y evaluated on S ′ , for which y was not evolved to fit, gives an estimation of ε g (y) on S ′ , and is denoted ˆε(y,S ′ ). The quantity ˆ G(y,S ′ ) := 1−ˆε(y,S ′ )/|S ′ | is the maximum likelihood estimator, and hence an approximation, of G g (y). 3 Analysis of Evolving Conjunctions The first target Boolean function that we analyse is the And n function of n≥ 2 inputs, i. e. And n (x 1 ,...,x n ) = x 1 ∧ x 2 ∧ ...∧ x n , that must be built from at least n− 1 binary And gates. In GP terminology, we have the 5 function set F =And and the terminal set T :=x i | i∈ [n]. Similar to the naming convention for the Max problem [16], but here without restricting the tree depth as it is not part of the problem definition, we adapt the name And n -And-x i | i ∈ [n] for this logic synthesis problem. Regarding the complete training set of this function, only one row of K And n has And n (α(x 1 ),...,α(x n )) = True when α(x 1 ) = ... = α(x n ) = True, all the other rows have the desired output False. To implement this synthesis in CGP, it suffices to set N in = n, N out = 1, use a lookup table with the single binary function And (i.e., K = 1 and k = 2), and choose N func ∈ N such that N func ≥ n− 1. It follows from [22] that the fitness of programs for And n -And-x i | i∈ [n] is monotonically improved (here decreased for the minimisation problem) as a function of the number of input variables used/included (connected to active nodes in case of CGP). Lemma 2 (Lemma 1 in [22]). On And n -And-x i | i ∈ [n], the truth table of a program currently using i distinct input variables differs from the target truth table of x 1 ∧ x 2 ∧ ...∧ x n at exactly f i = 2 n−i − 1 rows. We show that (1+1) CGP and (1+1) CGP ∗ with N func := D ≥ n− 1, using SAM mutation and the complete training set, synthesise the target function of And n -And-x i | i∈ [n] in expected time polynomial in D. In particular, for D ∈ [n− 1,∞)∩ O(n), the expected time is O(n 6 ) and the space required is O(n logn). Theorem 3. The (1+1) CGP and (1+1) CGP ∗ fit the complete training set of And n -And-x i | i∈ [n] using N func := D ≥ n−1, and SAM mutation inO nD 5 fitness evaluations in expectation and usesO(D logD) space to store its programs. If D ≥ 10, the probability that the number of fitness evaluations exceeds (1 + δ)20π 2 (n− 1)D 5 for any δ ≥ 1 is at most e −δ/3 . Proof. We apply the fitness level method to bound the expected running time. The search space X of valid programs is partitioned into n fitness levels and the (1+1) CGP is said to be at level i if its current program has i inputs connected to the output via its active function nodes. It follows from Lemma 2, and because 2 n−i − 1 is a monotone function, that the algorithm cannot fall down to a level below its current level. We then estimate for each level i∈ [n− 1] a lower bound s i on the probability of leaving the current level to a higher one. Our arguments will only consider strict improvement steps thus the implied result holds for both (1+1) CGP and (1+1) CGP ∗ . Another way to have D ≥ n− 1 is to assume that D = α(n− 1) for some α≥ 1. For a function node to be active, either an input edge of another function node (after it) or the output connection must be connected to it. So, for a program with i active function nodes at least i− 1 input edges of these nodes have been already used to maintain the node activeness, here the −1 takes into account the output connection. This leaves at most 2i− (i− 1) = i + 1 of the remaining input edges of these nodes to connect to the inputs, in other words the program can be at most at level i + 1. Conversely, a program at level i must have at least i− 1 active function nodes. We consider the following cases. Case 1: If there is at least one input edge of an active function node that can be redirected to an unused input, we then estimate the probability of this redirection in one iteration of the while-loop in SAM. The com- ponent associated with that input edge is selected for modification with probability 1 3D+1 , then the modification points the edge to one of the n−i unused inputs with probability n−i D+n−1 ≥ n−i 2D . Thus, the probability of leaving the current level in this case is at least n−i (3D+1)(2D) = (n−i)(D−i+1) (3D+1)(2D)(D−i+1) ≥ α(n−i) 2 (3D+1)(2D 2 ) . The last inequality holds because D−i+1≤ D and D−i+1 = α(n−1)−i+1 = αn−(αi−αi+α+i−1) = αn−(αi−(α−1)(i−1))≥ αn−αi for i≥ 1 and α≥ 1. Case 2: Otherwise, if no input edges of the active nodes can be redirected to an unused input to increase the current level, then there are exactly i− 1 active function nodes and at least D− (i− 1)≥ α(n−i) inactive function nodes. We then estimate the probability to activate one of these nodes and leave the current level within the three first iterations of the while-loop in SAM. In the first two iterations, we make some changes to the input edges of an inactive node by assuming the worst case that these changes are required. In the last iteration, we activate the node and this ends the while-loop in SAM. The probability to make a change to an input edge of an inactive node in the first iteration of the while-loop is at least 2·α(n−i) 3D+1 . Then this input edge is redirected to an unused input x u with a probability of at least 6 n−i D+n−1 ≥ n−i 2D . Let j be the inactive node associated with the input edge, our argument on what may happen in the two last iterations depends on the location of j. Subcase 2.1: Node j is located before the first (leftmost) active function node or there are no active function nodes at all. Let x v be the input that one input edge e of the first active function node is currently connected to, or that the output connection e is currently connected to if there is no active function nodes at all. In the second iteration, the algorithm redirects the other input edge of j (the one not selected in the first iteration) to x v , with a probability of at least 1 3D+1 · 1 D+n−1 ≥ 1 (3D+1)(2D) . To activate j in the third iteration, it suffices to redirect edge e to j, and the probability of this event is also at least 1 (3D+1)(2D) . By considering all three iterations, the overall probability to leave the current level i by SAM for this subcase is at least 2·α(n−i)·(n−i) (3D+1) 3 (2D) 3 = α(n−i) 2 (3D+1) 3 (4D 3 ) . Subcase 2.2: Node j is located after the first active function node. In the second iteration, we redirect the other input edge of j to the active function node j − that is located immediately before j, with a probability of at least 1 (3D+1)(2D) . In the last iteration, we redirect the connection e (which can be the output one) that currently maintains the activeness of j − to node j in order to activate j, with a probability of at least 1 (3D+1)(2D) . The overall probability to leave the current level i for this subcase is also at least α(n−i) 2 (3D+1) 3 (4D 3 ) . Combining all the cases gives that the probability to leave the current level i is at least s i := α(n−i) 2 (3D+1) 3 (4D 3 ) and summing their reciprocals over all the levels implies an expected running time of at most n−1 X i=1 (3D + 1) 3 (4D 3 ) α(n− i) 2 = (3D + 1) 3 4D 3 α −1 n−1 X i=1 1 i 2 ≤ (3D + 1) 3 4D 3 α −1 ζ(2) and this is (3D + 1) 3 D 3 ((n− 1)/D)(2π 2 /3) = O nD 5 . The space complexity follows by applying Lemma 1 with N func = D,k = 2 and N in = n =O(D). For D ≥ 10, we have that (3D + 1) 3 ≤ (3D + D/10) 3 < 30D 3 , the expected running time can be upper bounded by 20π 2 (n− 1)D 5 . Applying Lemma 10 with p i := α(n−i) 2 (3D+1) 3 (4D 3 ) thus p min = α (3D+1) 3 (4D 3 ) > D/(n−1) 120D 6 = 1 120(n−1)D 5 and n−1 X i=1 1 p 2 i = (3D + 1) 6 (16D 6 )α −2 n−1 X i=1 1 (n− i) 4 ≤ (30D 3 ) 2 (16D 6 )α −2 n−1 X i=1 1 i 4 ≤ 14400· D 12 · ((n− 1)/D) 2 · ζ(4) = 14400· D 10 (n− 1) 2 (π 4 /90) = 160π 4 (n− 1) 2 D 10 =: s, and with γ = 20π 2 δ(n− 1)D 5 , implies that the probability of exceeding the running time (1 +δ)20π 2 (n− 1)D 5 is at most exp − min 400π 4 δ 2 (n− 1) 2 D 10 4· 160π 4 (n− 1) 2 D 10 , 20π 2 δ(n− 1)D 5 4· 120(n− 1)D 5 ≤ e − π 2 minδ,δ 2 24 , and since minδ,δ 2 = δ for δ ≥ 1, this is less than e − δ 3 . The bound O(n 6 ) of the minimal setting D = n− 1 is tight and non-improvable for the (1+1) CGP ∗ when the initial program almost already fits the training set. Theorem 4. There exist initial programs for which the (1+1) CGP ∗ with N func := n− 1, and SAM mutation requires Ω(n 6 ) fitness evaluations in expectation to fit the complete training set of And n -And-x i | i∈ [n]. Proof. The initial programs correspond to those obtained at the penultimate level, each having a near-optimal fitness value of 1. A concrete example is the following. The first n− 2 function nodes are the only active ones and are connected to some n− 1 distinct input variables. This means the program output is currently pointed to the (n− 2)-th function node j. Meanwhile neither the remaining free variable v nor node j is connected to the last (inactive) function node j + . 7 Modifying any input connection of the first n− 2 nodes is not possible since this triggers termination of the while-loop in SAM and the produced solution is rejected by the strict selection as its fitness is at least 1. Modifying the connection of j + without creating an optimal program is also impossible. Therefore, SAM mutation is forced to produce an optimal solution in one call by redirecting the two input connections of j + to j and v, then by activating j + (this triggers the termination of the while-loop). Such an event requires SAM to run for some i ≥ 3 iterations in which the first i− 1 iterations only modify the components of node j + , with probability 3 3(n−1)+1 i−1 = 3 3n−2 i−1 , and the last iteration redirects the program output to j + , with probability 1 3(n−1)+1 · 1 n+(n−1)−1 = 1 (3n−2)(2n−2) . Conditioned on this, it still requires that among the first i− 1 iterations that at least one iteration redirects one input connection of j + to v, and another redirects the other input connection to j. The conditional probability for this by a union bound is at most i−1 2 2 3 · 1 2n−2 2 because two out of the three components associated with j + are for its input connections, and the probability of a successful redirection to a specific node is 1/(2n− 2). Summing the probability over all possible i gives the upper bound for the event, here we use (i− 1)/2≤ i− 2 that holds for i≥ 3: ∞ X i=3 3 3n− 2 i−1 · 1 (3n− 2)(2n− 2) · (i− 1)(i− 2) 2 2 3 · 1 2n− 2 2 ≤O(n −4 ) ∞ X i=3 (i− 2) 2 3 3n− 2 i−2 3 3n− 2 =O(n −5 ) ∞ X i=1 i 2 3 3n− 2 i =O(n −5 )· Li −2 3 3n− 2 =O(n −5 )· (3/(3n− 2))(1 + 3/(3n− 2)) (1− 3/(3n− 2)) 3 =O(n −6 ), Hence, the expected time for the (1+1) CGP ∗ to fit the complete training set is Ω(n 6 ). In contrast, the upper bound for the expected running time of (1+1) CGP can be further improved by considering neutrality in the fitness landscape as follows. We need the following lemma on a three-state Markov chain. The same chain was used in [2, 28] to analyse population diversity in Genetic Algorithms. Lemma 5. Consider the following Markov chain with three states with the absorbing state 3 and parameters p,q,r,s∈ [0, 1) where q,r > 0. 123 p q r s 1− p− q 1− r− s The expected time E 1 to reach the absorbing state 3 starting from state 1 is E 1 = q + r + s rq + rp + sp ≤ 1 r + 1 q + s rq . Moreover, if we have (p + q ≥ q ′ )∧ (r ≥ r ′ )∧ (s≤ s ′ ), then the above upper bound also holds with the bounding estimates, that is, E 1 ≤ 1 r ′ + 1 q ′ + s ′ r ′ q ′ . Proof. Let E i be the expected time to reach the absorbing state 3 starting from state i, then it is clear that E 3 = 0. By the law of total probability, the Markov chain satisfies the system of equations: E 1 = 1 + qE 2 + (1− p− q)E 1 (1) E 2 = 1 + sE 1 + (1− r− s)E 2 (2) 8 From (1), we get E 2 = (p+q)E 1 −1 q = p q + 1 E 1 − 1 q and substituting in (2) gives sE 1 = (r + s) p q + 1 E 1 − 1 q − 1 ⇔ r + s q + 1 = (r + s) p q + 1 − s E 1 . Therefore E 1 is E 1 = r+s q + 1 (r + s) p q + 1 − s = (r+s)+q q (r+s)(p+q)−sq q = q + r + s rq + rp + sp = (q + r + s)/(rq) (rq + rp + sp)/(rq) = 1 r + 1 q + s rq 1 + p q + sp rq ≤ 1 r + 1 q + s rq as 1 + p q + sp rq ≥ 1 and the first upper bound statement follows. To show the second bound, we start again from E 1 but divide both the numerator and denominator by r(p +q) (instead of rq in the previous calculation). This gives E 1 = (q + r + s)/(r(p + q)) (rq + rp + sp)/(r(p + q)) = q r(p+q) + 1 p+q + s r(p+q) 1 + sp r(p+q) ≤ 1 r ′ + 1 q ′ + s ′ r ′ q ′ since 1 + sp r(p+q) ≥ 1, q p+q ≤ 1, and p + q ≥ q ′ , r ≥ r ′ and s≤ s ′ . Theorem 6. The (1+1) CGP fits the complete training set of And n -And-x i | i∈ [n] using N func := D ≥ n− 1, SAM mutation in O(nD 4 ) fitness evaluations in expectation. Proof. Similarly to the proof of Theorem 3, we divide the search space into n levels according to the number of distinct inputs used, and the (1+1) CGP is said to be at level i ∈ [n] if its current program is connected to i distinct inputs. Again by Lemma 2 and by the elitist selection, it holds that once the algorithm has reached level i it cannot fall down to a level below i. We then estimate the expected time τ i to leave the current level i to a higher level. To estimate of τ i more precisely, by considering non-strict improvement steps as this is allowed by the (1+1) CGP, we partition each level i into two sublevels i + and i − which match exactly Cases 1 and 2 in the previous proof. That is, the algorithm is said to be at level i + (Case 1) if it has at least one input edge of an active node that can be redirected to an unused input, and it is at level i − (Case 2) otherwise. We then apply Lemma 5 with states 1, 2, 3 being levels i − ,i + ,i + 1 respectively, and τ i is bounded from above by E 1 of the lemma. It remains to bound the parameters p(i) +q(i),r(i),s(i) so that we can deduce an upper bound on E 1 (i). It follows from the same argument as in Case 1 of the previous proof that r(i)≥ n−i (3D+1)(2D) =: r ′ (i). To bound p(i) + q(i) from below, we follow Case 2, its subcases and use the same notation per subcase and the same assumption but make slightly different changes within only two iterations of SAM mutation because we only need to reach level i + (and not necessarily i + 1) from i − . In Subcase 2.1, the probability of selecting an input edge of an active function node j for change in the first iteration is still at least 2α(n−i) 3D+1 , but then it suffices to redirect that edge to x v thus with probability 1 D+n−1 ≥ 1 2D , then in the second iteration to redirect edge e (either of the output or of the first active function node) to j, with a probability of at least 1 (3D+1)(2D) . In Subcase 2.2, we redirect the selected input edge of the function node j to the first active node j − before j in the first iteration with probability 1 D+n−1 ≥ 1 2D , then redirect edge e to j in the second iteration with a probability of at least 1 (3D+1)(2D) . Therefore, we have that the probability of transiting from state i − to at least i + is p(i) + q(i)≥ 2α(n−i) (3D+1) 2 (2D) 2 = : q ′ (i). To bound s(i) from above, we note that for the algorithm to be in level i + its current program must either have at least one input with multiple input connections from active function nodes to it, or have at least one 9 active function node whose activeness is maintained by multiple input connections from other active function nodes. In the former case, for an upper bound argument on s(i), we only need to focus one such input and two specific connections from the active nodes to the input because to return to level i − at least one of the connections must no longer come from an active node. In other words, there are at most two active nodes that can be deactivated/changed to return to level i − , and this happens with a probability of at most 2· 1 3D+1 by one SAM mutation. The argument is similar for the later case as again we only need to focus on one active function node and two specific connections that maintain the node activeness. Therefore, we have s(i)≤ 2 3D+1 =: s ′ (i). Applying Lemme 5 and summing all τ i give the expected running time: n−1 X i=1 τ i ≤ n−1 X i=1 1 r ′ (i) + 1 q ′ (i) + s ′ (i) r ′ (i)q ′ (i) = (3D + 1)(2D) + (3D + 1) 2 (2D) 2 (2α) −1 n−1 X i=1 1 n− i + 2(3D + 1) 2 (2D) 3 (2α) −1 n−1 X i=1 1 (n− i) 2 =O nD 3 H n−1 +O(nD 4 )ζ(2) =O(nD 4 ). The analyses from Theorems 3 and 6 show that using more than the minimum n− 1 function nodes can benefit CGP by increasing the bounds s i in the harder case, and also q ′ (i) for p(i) + q(i) in the Markov chain. 4 Analysis of Evolving Exclusive Disjunctions The second target function that we consider is the Xor n function of n ≥ 2 inputs where Xor n (x 1 ,...,x n ) : = x 1 ⊕x 2 ⊕...⊕x n that must be built from at least n− 1 binary Xor gates. This function is of interest for us because it is not evolvable [38] even though it is PAC-learnable [37] thus a candidate problem to show a negative result for CGP, especially for an advanced operator like SAM. We adopt the name Xor n -Xor-x i | i∈ [n] for this problem. A candidate CGP program is a function whose raw form may contain an input variable repeated multiple times, e. g. x 1 ⊕x 1 ⊕x 2 where x 1 is repeated twice. However, a variable that is repeated an even number of times is as if it is ignored, and it is repeated an odd number of times is as if it is repeated once. We refer to the function form after applying these simplifications as the simplified form. For the Xor n -Xor-x i | i ∈ [n] and using the complete training set K Xor n , the fitness of a candidate program y can only take two possible values, that is, f (y) = 0 if the simplified form of y is exactly Xor n , i. e. every input appears an odd number of times in the raw form, otherwise f (y) = 2 n−1 , i. e. y is incorrect on a half of the rows (and correct on the other half) [22]. This property implies that if the use of an incomplete training set leads to a program that ignores some inputs in the simplified form, then the generalisation ability of such a program is always 2 n−1 /2 n = 1/2. This is as bad as a random guess, and justifies our focus on the setting of the complete training set S =K Xor n . We then expect CGP to perform a random walk in the space of programs until it realises an optimal program, i. e. having the simplified form Xor n . To show an exponential time on reaching such a program, we first show that it is unlikely that such a program can emerge from a fixed subset L of function nodes. For a lower bound argument, it suffices to focus on two necessary properties of an optimal program built out of L: (i) every input is connected to L by an odd number of connections; (i) the output of at least n− 2 nodes of L is connected to other nodes in L. The second property is required because an optimal program has at least n− 1 active function nodes, thus at least n− 2 of those have their activeness maintained by L. Formally, an input variable x i is called an odd variable with respect to L if it is connected to L by an odd number of connections, otherwise it is an even variable (with respect to L, we often omit this part when L is clear from the context). Thus we track the number 10 of odd variables, denoted V (L), and U (L) := |ℓ ∈ L | the output of ℓ is connected to another node in L| of the current program in CGP to reach their respective values n and n− 2. Lemma 7. A randomly generated CGP program on Xor n -Xor-x i | i∈ [n] using N func := D ≥ n− 1 has V (L)≤ 3n/4 with probability 1− e −Ω(n) , for any fixed set L of function nodes with m :=|L|∈ poly(n). Proof. We are only interested in the sampling steps where the 2m connections of L are sampled to connect to an input variable because those are the only steps that can change V (L). Let V j be V (L) of the sampled program after the j-th step and we apply the negative drift theorem (Theorem 11) with potential X j := n−V j . Note that X 0 = n as no connections of L have been sampled yet and zero is an even number, and that |X j+1 − X j | = 1 as the sampling toggles the parity of exactly one input variable. Each considered sampling step chooses a input variable x 1 ,...,x n uniformly at random. Thus for X j ∈ [n/4, 3n/8], there are at least V j = n−X j ≥ n− 3n/8 = 5n/8 odd variables, which increase X j if one is chosen. Otherwise if an even variable is chosen then X j is decreased. Thus, we have a drift E [X j+1 − X j | X j ∈ [n/4, 3n/8]]≥ 5/8− 3/8 = 1/4. Applying Theorem 11 with parameters a = n/4, b = 3n/8, r(ℓ) = 1, and δ = 1/4, we obtain for T = minj ∈ N | X j ≤ n/4 that P (T ≤ e εn ) ≤ e −Ω(n) for a suitable constant ε > 0. Since T > 2m implies the final V (L) of the initialisation is below 3n/4, thus event T > 2m ⊆ final V (L) < 3n/4 and we get Pr (final V (L) < 3n/4) ≥ Pr (T > 2m) = 1− Pr (T ≤ 2m) ≥ 1− Pr (T ≤ e εn ) ≥ 1− e −Ω(n) as 2m ≤ e εn for sufficiently large n. If an optimal program has not yet been found, then the (1+1) CGP always accepts offspring programs and all modifications by every iteration of the while-loop across SAM mutations are taken into account. We refer to each of these iterations as an elementary step. The following lemma, again using the negative drift theorem, shows that it is unlikely for a program with the two necessary properties, let alone for an optimal program, to emerge during the application of an exponential number of elementary steps to a randomly generated program. Lemma 8. Starting from a randomly generated CGP program on Xor n -Xor-x i | i ∈ [n] using N func := D ≥ n− 1, for a fixed set L of its function nodes with m :=|L|≤ (1 +d)n for any d≤ 10 −2 , the probability that a program with U (L)≥ n− 2 and V (L) = n emerges during the application of e εn elementary steps of SAM for some constant ε > 0 is at most e −Ω(n) . Proof. For m < n− 1, the result is trivial as V (L) cannot reach n, so we assume the opposite. Let U j and V j be min(U (L),n− 2) and V (L) respectively after applying j elementary steps. We can also neglect all steps where U j and V j are unchanged as including those can only increase the number of required steps. We apply the negative drift theorem with potential Y j := 2n− 2− U j − V j . In any single iteration, the configuration of at least n− 2 input variables remains unchanged, so |V j+1 − V j | ≤ 2. Since only one link is modified per iteration, it is clear that|U j+1 −U j |≤ 1. Therefore,|Y j+1 −Y j |≤ 3 by triangle inequality. Further, V j is bounded from above by n, and U j is by n− 2. It follows from Lemma 7, that V 0 ≤ 3n/4 with probability 1− e −Ω(n) . Assuming this occurs then Y 0 ≥ 2n−2−(n−2)−3n/4≥ n/4, and we estimate the drift E[Y j+1 −Y j | Y j ] in the interval Y j ∈ [n/256−2,n/128−2]. In this interval it holds that U j = 2n− 2− Y j − V j ≥ 2n− 2− ( n 128 − 2)− n = 127n 128 (3) V j = 2n− 2− Y j − U j ≥ 2n− 2− ( n 128 − 2)− (n− 2)≥ 127n 128 + 2(4) To increase Y j , it suffices to select a connection pointing to an odd variable and reconnect it to another odd variable (w. r. t. L), i. e. with probability at least V j 2m · V j − 1 n + m− 1 (4) > (127n/128) 2 (2m) 2 > 6n 2 25D 2 = : p + . 11 for n sufficiently large. This increases Y t by two. There are also other possibilities to increase Y t but we assume they only contributes zero to the drift. To decrease Y j , it is necessary that one of the following two events happens. Note that some subsequent change following those events may lead to eventually no change in Y j , but we pessimistically assume that Y j always is decreased by 3. (A) Select a connection pointing an even variable (then reconnect it). (B) Select a connection not pointing to an input variable and either reconnect it to an even variable, or reconnect it to a function node of L which is not currently counted in U (L). There are at most 2D− U j − V j ≤ 2n + 2dn− U j − V j = 2dn + 2 + Y j ≤ n/128 + 2dn connections pointing to an even variable, thus Pr (A)≤ (n/128 + 2dn)/(2m)≤ 1/128 + 2d. Here we use n/(2m)≤ n/(2(n− 1))≤ 1 for n≥ 2. It follows from (3) that at most D− 1−U j ≤ n +dn− 1− 127n/128 < n/128 +dn function nodes have their output not used within L, and from (4) that there are at most n−V j ≤ n−(127n/128−2) < n/128 even variables. Note that there are at least n choices for reconnection, so Pr (B) ≤ (n/128 + dn)/n + n/(128n) ≤ 1/64 + d. Here we assume that the probability of selecting the right connection type is at most 1. So one of the two events happens with probability at most Pr (A) + Pr (B)≤ 1 128 + 2d + 1 64 + d < 1 42 + 3d = : p − . Since Y j can only decrease by at most three in each iteration, we obtain for the drift for n sufficiently large and any d≤ 10 −2 that E h Y j+1 − Y j | Y j ∈ [ n 256 − 2, n 128 − 2] i > 2· p + − 3· p − = 12n 2 25D 2 − 3 42 − 9d = n D 12n 25D − 3D 42n − 9Dd n ≥ 1 1 + d 12 25(1 + d) − 3(1 + d) 42 − 9(1 + d)d > 1 1 + 10 −2 12 25(1 + 10 −2 ) − 3(1 + 10 −2 ) 42 − 9(1 + 10 −2 )10 −2 > 3 10 = : δ. Applying Theorem 11 with parameters a = n/256 − 2, b = n/128 − 2, r(ℓ) = 3 and δ we obtain for T := minj ∈ N| Y j ≤ a that P (T ≤ e −εn )≤ e −Ω(n) for a suitable constant d > 0. Hence, even including the event at initialisation, with probability at least 1− e −Ω(n) for n sufficiently large, we still have Y j > n/256 and thus U j + V j < 2n− 2, or equivalently (V j < n)∨ (U j < n− 2) throughout the application of e εn elementary steps. To extend the lemma to (1+1) CGP, we take a union bound over all subsets L, whose number can be estimated via the approximation of the standard binomial coefficient bounds using binary entropy. Finally, the SAM while-loop terminates once the output connection is selected for modification, which occurs with probability 1/(3D + 1) = Ω(1/n) for D = O(n). Hence, an exponential number of elementary SAM steps translates to the same order of SAM mutations (fitness evaluations) by a Chernoff bound. Theorem 9. Let d < 10 −2 be a sufficiently small constant. The probability that the (1+1) CGP fails to fit the complete training set of Xor n -Xor-x i | i ∈ [n] within e Ω(n) fitness evaluations using SAM mutation and N func := D for n− 1≤ D ≤ n + dn, is 1− e −Ω(n) . Proof. It follows from Lemma 8 that the probability that an optimal program emerges from a fixed subset L of m function nodes with m∈ [n− 1,n +dn] is at most e −Ω(n) ≤ e −κn after applying e εn elementary steps of SAM to a randomly generated program for some constants κ > 0 and ε > 0. By a union bound over all possible such subsets L, we get a required running time for the (1+1) CGP in terms of number of elementary steps. Since we 12 AND n param. SettingGP param.Setting Dimension n 3,..., 15 (compl.), 3,..., 50 (incompl.)Maximum iterations1× 10 6 Input i∈0, 1Search strategy(1+1) Function setF =AndSelection typesnon-strict, strict Terminal setT =x 1 ...x n No. replications per n30 Table 1: Configuration of GP and And n for the experiments. may assume that D ≤ n + dn≤ 2n− 2, we may estimate the number of such subsets by D X i=n−1 D i ≤ (D− n) D n− 1 ≤ (D− n)2 D·H((n−1)/D) for n sufficiently large where H(α) = −α logα− (1− α) log(1− α) for α ∈ (0, 1) denotes the binary entropy function. The last inequality uses n k ≤ 2 nH(k/n) , which holds for all k ∈ [n] (see for example [3]). Note that H(α) is strictly monotone decreasing in α ∈ [1/2, 1), and that (n− 1)/D ≥ 1/(1 + d + o(1)) and hence, D·H((n− 1)/D)≤ n· (1 +d)·H(1/(1 +d +o(1))) < nκ ′ < nκ for a suitable constant κ ′ > 0, thus the required running time is still exponential. To count this time in terms of fitness evaluations, we note that for a SAM mutation, its while-loop ends if the output node is chosen for modification, i. e. with probability at least 1/(3D + 1) = Ω(1/n). Now consider a sum X of e dn Bernoulli random variables, each becoming one if the output is selected for modification and zero otherwise. Then because a SAM mutation can also be stopped by modifying an active function node, X is a lower bound for the number of fitness evaluations. By a classical Chernoff bound, we have that Pr(X ≥ e cn ) = 1− e −Ω(n) for a sufficiently small constant c > 0, and this concludes our proof. 5 Experiments We evaluate CGP and TGP on And n through two sets of experiments. First, using the complete training set, we measure runtime to highlight the performance gap between the two approaches when evolving the exact solution. Second, with incomplete training and testing sets, we assess both runtime and generalisation ability to examine their generalisation performance. Experimental setup: We used TinyverseGP [13], a modular benchmarking Python library for GP that provides modules for various flavours of GP including CGP and TGP, to perform the experiments. Using the existing implementations TinyTGP and TinyCGP of the library, we derived the models SimpleTGP and SimpleCGP which correspond to (1 + 1) TGP/CGP as described in Section 2.1 and [16, 15]. The CGP model uses MutationSAM as described in Algorithm 3, while the TGP model uses the mutations from [15] which are based on the HVL-prime operator [27]. The implementations of the models and the And n as well as the raw data obtained in the experiments are provided in our repository 1 . We evaluated various settings of n in each scenario. For the scenario where the complete training set is used, we evaluated n∈3,..., 15. However, since the evaluation of an incomplete training set is less expensive, we evaluated the performance for larger settings of n ∈ 3,..., 50 in this scenario. For each value of n, 30 runs were performed with different random seeds per model (CGP and TGP). The mean of each sample per n was then used for the illustration of our results. The GP configuration used in our experiments is summarised in Table 1. Running time was measured as the number of iterations for the algorithm to fit the training set. In our plots, we refer to the TGP models as simple tgpsingle and simpletgpmulti and to the CGP model as simplecgpsam. For CGP, we defined the length of the genotype N func with respect to the dimension n but also considered extra nodes to see if there is any gap in runtime. More precisely, we used N func ∈ n, 2n, 3n, and refer to as 1n, 2n, 3n in our results. 1 https://github.com/GPBench/TinyverseGP/tree/ppsn-2026 13 Figure 2: Results of the comparison on And n using complete datasets. We set the size of the incomplete training and testing sets S and S ′ as|S| =|S ′ | =⌈n k ⌉ with k = 1.3 for the settings of large n. Both sets were generated uniformly at random. Approximating the generalisation ability G g (y) by ˆ G(y,S ′ ) was done with the formula as explained in Section 2.2. Statistics are reported per setting of n excluding unsuccessful runs, i. e. exceeding the maximum number of iterations without fitting the training set. Results: Figure 2 shows the results for the running time comparison on And n when the complete training set was used. It can be clearly seen that the considered TGP models perform generally better in this scenario. It can also be seen that increasing the number of function nodes generally improves the search performance of CGP while using strict selection deteriorates its performance. Figure 3 show the results of our experiments with incomplete training and testing sets and it can also be seen that increasing the number of function nodes improves the search performance of CGP in terms of running time for both selection strategies. It is also evident that the generalisation error is relatively low for all models considered demonstrating good generalisation abilities on And n . Detailed statistical evaluation of the results can be found in the appendix document. 6 Conclusions and Discussions We presented the first runtime analysis of CGP for evolving conjunctions and disjunctions, considering both complete and incomplete training sets. For And n with n variables and D nodes, we proved expected runtimes of O(nD 5 ) for (1+1) CGP ∗ and O(nD 4 ) for (1+1) CGP with the complete training set. Our analysis revealed the characteristics of CGP induced search that enabling the acceptance of equally good solutions with active gates non-contributing to fitness is beneficial. We also showed that (1+1) CGP fails with overwhelming probability on the complete training set of the Xor n . To complement our theoretical analysis, we conducted an empirical study examining the runtime performance and generalisation ability of CGP and TGP models for And n . The theoretical analysis of incomplete training sets for Xor n is left out for the reason that the generalisation ability one can hope for is only as good as a random guess. For And n , there is a technical obstacle that on an incomplete training set, our approach using the fitness-level method and Markov chain analysis no longer works with the current level partition. In particular, it is possible to swap a larger set of input variables for a smaller one, and such a change still improves the fitness. The same issue must occur for TGP under a global mutation operator, however we could not find any literature on this. We also believe drift analysis [6] is a better-suited tool for addressing such a setting, and leave the analysis for future work. Future work should also include extending the analysis to general Boolean formulas with AND/OR, identifying broader function classes where CGP is effective, and studying its behaviour on flat fitness landscapes. Achieving these, however, requires a deeper understanding of the underlying dynamics of CGP, which still is largely unexplored. 14 Figure 3: Results of the comparison on And n using incomplete datasets. References [1] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2009) [2] Corus, D., Oliveto, P.S.: Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms. IEEE Transactions on Evolutionary Computation 22(5), 720–732 (2018) [3] Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley (2006) [4] Cramer, N.L.: A representation for the adaptive generation of simple sequential programs. In: Proceedings of the 1st International Conference on Genetic Algorithms. p. 183–187. Lawrence Erlbaum Associates (1985) [5] Dickmanns, D., Schmidhuber, J., Winklhofer, A.: Der genetische algorithmus: Eine implementierung in prolog. Fortgeschrittenenpraktikum, Institut f ur Informatik, Lehrstuhl Prof. Radig, Technische Universit at Munchen (1987) [6] Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: GECCO ’10: Proceedings of the 12th annual conference on Genetic and Evolutionary computation. p. 1449–1456. ACM (2010) [7] Doerr, B., Lissovoi, A., Oliveto, P.S.: Evolving boolean functions with conjunctions and disjunctions via genetic programming. In: GECCO ’19: Proceedings of the Genetic and Evolutionary Computation Conference. p. 1003–1011. ACM (2019) [8] Doerr, B., Lissovoi, A., Oliveto, P.S.: (1+1) genetic programming with functionally complete instruction sets can evolve boolean conjunctions and disjunctions with arbitrarily small error. Artificial Intelligence 319, 103906 (2023) 15 [9] Goldman, B.W., Punch, W.F.: Reducing wasted evaluations in cartesian genetic programming. In: Eu- roGP’13: Proceedings of the 16th European conference on Genetic Programming. Lecture Notes in Com- puter Science, vol. 7831, p. 61–72. Springer (2013) [10] Hachtel, G.D., Somenzi, F.: Logic synthesis and verification algorithms. Kluwer (1996) [11] Husa, J., Sekanina, L.: Evolving cryptographic boolean functions with minimal multiplicative complexity. In: IEEE Congress on Evolutionary Computation, CEC 2020. IEEE (2020) [12] Kalkreuth, R., Droschinsky, A.: On the time complexity of simple cartesian genetic programming. In: IJCCI 2019: Proceedings of the 11th International Joint Conference on Computational Intelligen. p. 172–179. ScitePress (2019) [13] Kalkreuth, R., de Fran ̧ca, F.O., Jankovic, A., Anastacio, M., Dierkes, J., Vasicek, Z., Hoos, H.: Tiny- versegp: Towards a modular cross-domain benchmarking framework for genetic programming. In: GECCO ’25 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion. p. 127–130. ACM (2025) [14] Kalkreuth, R., Vaˇs ́ıˇcek, Z., Husa, J., Vermetten, D., Ye, F., B ̈ack, T.: General boolean function benchmark suite. In: Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. p. 84–95 (2023) [15] K ̈otzing, T., Sutton, A.M., Neumann, F., O’Reilly, U.M.: The max problem revisited: The importance of mutation in genetic programming. In: GECCO ’12: Proceedings of the 14th annual conference on Genetic and evolutionary computation. p. 1333–1340. ACM (2012) [16] K ̈otzing, T., Sutton, A.M., Neumann, F., O’Reilly, U.M.: The max problem revisited: The importance of mutation in genetic programming. Theoretical Computer Science 545, 94–107 (2014) [17] Koza, J.R.: Hierarchical genetic algorithms operating on populations of computer programs. In: Proceed- ings of the 11th international joint conference on Artificial intelligence - Volume 1. p. 768–774. Morgan Kaufmann (1989) [18] Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press (1993) [19] Lissovoi, A., Oliveto, P.S.: On the time and space complexity of genetic programming for evolving boolean conjunctions. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. AAAI Press (2018) [20] Lissovoi, A., Oliveto, P.S.: On the time and space complexity of genetic programming for evolving boolean conjunctions. Journal of Artificial Intelligence Resesearch 66, 655–689 (2019) [21] Lissovoi, A., Oliveto, P.S.: Computational complexity analysis of genetic programming. In: Theory of Evo- lutionary Computation - Recent Developments in Discrete Optimization, p. 475–518. Natural Computing Series, Springer, Cham, Switzerland (2020) [22] Mambrini, A., Oliveto, P.S.: On the analysis of simple genetic programming for evolving boolean functions. In: Proceedings of the 19th European Conference on Genetic Programming, EuroGP 2016. p. 99–114. Springer (2016) [23] Miller, J.F.: An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In: GECCO’99: Proceedings of the 1st Annual Conference on Genetic and Evolu- tionary Computation - Volume 2. vol. 2, p. 1135–1142. Orlando, Florida, USA (1999) 16 [24] Miller, J.F., Smith, S.L.: Redundancy and computational efficiency in cartesian genetic programming. IEEE Transactions on Evolutionary Computation 10(2), 167–174 (2006) [25] Miller, J.F., Thomson, P.: Cartesian genetic programming. In: Genetic Programming: European Confer- ence, EuroGP 2000. p. 121–132. Springer Berlin Heidelberg, Berlin, Heidelberg (2000) [26] Miller, J.F.: An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Com- putation - Volume 2. p. 1135–1142. Morgan Kaufmann (1999) [27] Neumann, F., O’Reilly, U.M., Wagner, M.: Computational complexity analysis of genetic programming - initial results and future directions. In: Genetic Programming Theory and Practice IX, p. 113–128. Springer New York (2011) [28] Oliveto, P.S.: Time complexity analysis of stochastic search algorithms. In: Handbook of Heuristics (Second Edition), p. 849–884. Springer, Cham, Switzerland (2025) [29] Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3), 369–386 (2011) [30] Oliveto, P.S., Witt, C.: Erratum: Simplified drift analysis for proving lower bounds in evolutionary com- putation. CoRR abs/1211.7184 (2012) [31] Openshaw, S., Turton, I.: Building new spatial interaction models using genetic programming. In: Evolu- tionary Computing, , AISB workshop. p. 11–13. Springer Berlin Heidelberg (1994) [32] Perkis, T.: Stack-based genetic programming. In: Proceedings of the First IEEE Conference on Evolution- ary Computation. p. 148–153. IEEE Press (1994) [33] Poli, R.: Parallel distributed genetic programming. Technical Report CSRP-96-15, School of Computer Science, University of Birmingham (1996) [34] Ryan, C., Collins, J.J., O’Neill, M.: Grammatical evolution: Evolving programs for an arbitrary language. In: Proceedings of the First European Workshop on Genetic Programming. p. 83–96. Springer (1998) [35] Turner, A.J., Miller, J.F.: Cartesian genetic programming: Why no bloat? In: EuroGP 2014: Revised Selected Papers of the 17th European Conference on Genetic Programming. p. 222–233. Springer (2014) [36] Turner, A.J., Miller, J.F.: Neutral genetic drift: an investigation using cartesian genetic programming. Genetic Programming and Evolvable Machines 16(4), 531–558 (2015) [37] Valiant, L.G.: A theory of the learnable. In: STOC’84: Proceedings of the sixteenth annual ACM sympo- sium on Theory of Computing. p. 436–445. ACM (1984) [38] Valiant, L.G.: Evolvability. Journal of ACM 56(1), 3:1–3:21 (2009) [39] Vas ́ıcek, Z.: Cartesian GP in optimization of combinational circuits with hundreds of inputs and thousands of gates. In: Genetic Programming - 18th European Conference, EuroGP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings. p. 139–150. Springer (2015) [40] Vas ́ıcek, Z., Sekanina, L.: Evolutionary approach to approximate digital circuits design. IEEE Transactions on Evolutionary Computation 19(3), 432–444 (2015) [41] Vas ́ıcek, Z., Sekanina, L.: Evolutionary design of complex approximate combinational circuits. Genetic Programming and Evolvable Machines 17(2), 169–192 (2016) [42] Witt, C.: Fitness levels with tail bounds for the analysis of randomized search heuristics. Information Processing Letters 114(1-2), 38–41 (2014) 17 [43] Yu, T., Miller, J.: Neutrality and the evolvability of boolean function landscape. In: Genetic Programming. p. 204–217. Springer Berlin Heidelberg (2001) A Useful Tools for the Analysis The following tail bounds for sums of geometric random variables are from [42]. Lemma 10 (Theorem 1 in [42]). Let (X i ) i∈[n] be n independent random variables following geometric distribu- tions with the corresponding success probabilities (p i ) i∈[n] , and define X := P n i=1 X i , p min := minp i | i∈ [n]. If s≥ P n i=1 (1/p 2 i ) for some s <∞ then Pr (X ≥ E [X] + γ)≤ e − γ 4 ·min γ s ,p min and Pr (X ≤ E [X]− γ)≤ e − γ 2 2s . The negative drift theorem is from [29, 30]. Theorem 11 (Theorem 2 in [30]). Let (X t ) t∈N be a real-value stochastic process over some state space. Suppose there exist an interval [a,b] ⊂ R, two constants δ,ε > 0, and possibly depending on ℓ := b− a a function r(ℓ) such that 1≤ r(ℓ) = o(ℓ/ logℓ) such that for all t≥ 0 the following conditions hold: 1. E [X t+1 − X t | X t ,a < X t < b]≥ ε, 2. Pr (|X t+1 − X t |≥ j | X t ,a < X t )≤ r(ℓ) (1+δ) j for j ∈ N. Then there exists a constant c > 0 such that for T := mint≥ 0| X t ≤ a it holds that Pr T ≤ 2 cℓ/r(ℓ) | X 0 ≥ b = 2 −Ω(ℓ/r(ℓ)) . B Additional Statistical Evaluation of the Experimental Results Table 2 shows the statistical evaluation for the comparison of running time between TGP and CGP on And n using non-strict and strict selection as well as complete datasets. 18 SelectionnModelSuccessful Runs Avg. IterationsSDMin Q1 Median Q3Max strict 3 simple cgpsamstrict1n301932031017167 simplecgpsamstrict2n30814002861 simple cgpsamstrict3n3035000418 simpletgpmultistrict3011122481460 simpletgpsinglestrict301282681830 4 simple cgpsamstrict1n2920648321129851985 simplecgpsamstrict2n301748070212254439 simplecgpsamstrict3n30245701614304 simple tgpmultistrict30161018152247 simpletgpsinglestrict302010712182547 5 simplecgpsamstrict1n292002735913519883339909 simple cgpsamstrict2n3010223841218501062 simplecgpsamstrict3n30481090102033595 simpletgpmultistrict30221458203354 simple tgpsinglestrict302918516243880 6 simplecgpsamstrict1n205055143151338224241863331 simplecgpsamstrict2n30146287221501031396 simple cgpsamstrict3n3012430001231961322 simpletgpmultistrict302515817242883 simpletgpsinglestrict3047328274258168 7 simplecgpsamstrict1n15349068091733304756822293314957 simplecgpsamstrict2n304061114291083174105451464 simplecgpsamstrict3n309313220305897715 simple tgpmultistrict3036171024285077 simpletgpsinglestrict3045211629445997 8 simple cgpsamstrict1n175884913892913434411375741548412 simplecgpsamstrict2n30115334505643844362148245973 simplecgpsamstrict3n3011222840227614445613817 simpletgpmultistrict3040191124365391 simple tgpsinglestrict30662924436476149 9 simplecgpsamstrict1n0------- simplecgpsamstrict2n3098902904234966276977158233 simplecgpsamstrict3n30768207613491042188521 simpletgpmultistrict3047161740475687 simpletgpsinglestrict30693036495778166 10 simplecgpsamstrict1n0------- simplecgpsamstrict2n3075392029819120517198288716 simplecgpsamstrict3n302561530840112306164522711 simpletgpmultistrict30592527385668121 simpletgpsinglestrict308337215771105165 11 simplecgpsamstrict1n0------- simplecgpsamstrict2n302138045778121544624115308232758 simplecgpsamstrict3n301503150296261282723407271033 simpletgpmultistrict30783924547091210 simpletgpsinglestrict308727317284103144 12 simplecgpsamstrict1n0------- simplecgpsamstrict2n282939338093727071324240215136393 simplecgpsamstrict3n3068281653950292481315277503 simple tgpmultistrict30812536628098129 simpletgpsinglestrict30122526180114144263 13 simplecgpsamstrict1n0------- simplecgpsamstrict2n304836052182145105183600857160198080 simplecgpsamstrict3n3014865387637535014055457175512 simpletgpmultistrict30813222597997161 simple tgpsinglestrict30111504378101136222 14 simple cgpsamstrict1n0------- simplecgpsamstrict2n22342333449927336632319252189105703 simplecgpsamstrict3n29123131891417064916031875264404 simpletgpmultistrict3010034497894116189 simpletgpsinglestrict301373788112135158225 15 simple cgpsamstrict1n0------- simplecgpsamstrict2n1898201715142413382954512655660 simplecgpsamstrict3n2788121428913140611031097843166 simple tgpmultistrict30113435187108128214 simpletgpsinglestrict30137565085133168289 non-strict 3 simplecgpsamnonstrict1n3011150171452 simplecgpsamnonstrict2n3035002523 simplecgpsamnonstrict3n3046001429 simpletgpmultinonstrict301071581431 simple tgpsinglenonstrict3014916122242 4 simplecgpsamnonstrict1n3043412182952200 simplecgpsamnonstrict2n3017210492075 simple cgpsamnonstrict3n30152302617101 simpletgpmultinonstrict3014827121832 simpletgpsinglenonstrict302216411162871 5 simple cgpsamnonstrict1n3012816923368109710 simplecgpsamnonstrict2n30621030192553493 simplecgpsamnonstrict3n3026290101734148 simpletgpmultinonstrict302110813182942 simpletgpsinglenonstrict302814719243758 6 simplecgpsamnonstrict1n302131792572131325717 simplecgpsamnonstrict2n3066450395886181 simplecgpsamnonstrict3n30453610203561157 simpletgpmultinonstrict302715515244060 simpletgpsinglenonstrict3034161122324684 7 simplecgpsamnonstrict1n30319303261341884381436 simplecgpsamnonstrict2n301159864598138386 simplecgpsamnonstrict3n3064611284671281 simpletgpmultinonstrict303516627324874 simpletgpsinglenonstrict30543226334466187 8 simplecgpsamnonstrict1n30623732562543966963812 simplecgpsamnonstrict2n30150127557104226525 simplecgpsamnonstrict3n30118135183470130608 simpletgpmultinonstrict3038161725385067 simpletgpsinglenonstrict30673317466084164 9 simplecgpsamnonstrict1n301248104695294112420253372 simplecgpsamnonstrict2n3029622543118196444967 simplecgpsamnonstrict3n301391102264104192524 simpletgpmultinonstrict30492715334458166 simpletgpsinglenonstrict30793632527094191 10 simplecgpsamnonstrict1n3014191042152701131116793986 simplecgpsamnonstrict2n30326234411532644041015 simplecgpsamnonstrict3n30295399491101612561792 simpletgpmultinonstrict30521916384863101 simpletgpsinglenonstrict30863332648099172 11 simplecgpsamnonstrict1n30234818803291081197029099072 simplecgpsamnonstrict2n30375281681912985021101 simplecgpsamnonstrict3n302341992686166302781 simpletgpmultinonstrict30572220405570128 simpletgpsinglenonstrict3010846477294134218 12 simplecgpsamnonstrict1n302824351324011851772237418617 simplecgpsamnonstrict2n30595358603445287901545 simple cgpsamnonstrict3n3031723335127242465806 simpletgpmultinonstrict30692628526781126 simple tgpsinglenonstrict30112415180100141206 13 simplecgpsamnonstrict1n30273218544401395234435068635 simplecgpsamnonstrict2n3096910974427271413455627 simplecgpsamnonstrict3n30424373381582984721402 simpletgpmultinonstrict30712831536387127 simpletgpsinglenonstrict30120404591108141241 14 simplecgpsamnonstrict1n304608343876725763742644015033 simplecgpsamnonstrict2n3080773814039661210923992 simplecgpsamnonstrict3n30504662551963384573030 simple tgpmultinonstrict308630396580101167 simpletgpsinglenonstrict30122395695122148226 15 simplecgpsamnonstrict1n304782321969828703598530413031 simplecgpsamnonstrict2n30109399922953275412065107 simple cgpsamnonstrict3n306405041112775318152240 simple tgpmultinonstrict309621398496112144 simpletgpsinglenonstrict301354368110121159219 Table 2: Results for the runtime comparison between TGP and CGP on And n for n ∈ 3,..., 15 using complete datasets. Note that for 1n, CGP failed to evolve solutions for n > 9 with strict selection. 19