💻 computer science

Complexity Theory of Randomised Testing

This paper establishes the first complexity-theoretic foundations for randomised testing by modeling generators as Turing transducers to characterize the limits of efficient and space-bounded input generation, revealing fundamental distinctions between generation and decision complexity while proving that efficient generation requires specific certificate schemes and cannot be compositionally derived from general logical predicates.

Original authors: Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

Published 2026-07-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a video game developer trying to test a new, massive world. You want to make sure your game doesn't crash, so you need a robot that can spit out millions of random levels, characters, and items to see if anything breaks. This robot is called a generator. For years, developers have built these robots by hand, tweaking them until they work well enough. But nobody really knew the theoretical limits of what these robots could actually do. Could they generate any possible level? Could they do it fast enough to be useful?

A team of researchers from Imperial College London and Kaihong decided to put these robots under a microscope using Complexity Theory—the math that studies how hard problems are to solve. They didn't just look at the code; they modeled the robots as "Turing machines" (the ultimate theoretical computers) that eat random bits of data and spit out game levels. Here is what they discovered.

The "What Can Be Made" List

First, they asked: What is the absolute limit of what a generator can produce?

They found that if you give a generator unlimited time and memory, it can produce exactly the same set of things that a standard computer can recognize. In the world of math, this is called Recursively Enumerable (RE) languages.

The Good News: If a set of inputs (like "all valid C programs") can be recognized by a computer, a generator can theoretically produce them.
The Bad News: If a set of inputs is too weird to be recognized by a computer (like "all programs that will never stop running"), no generator can ever produce them. It's not a bug in your code; it's a fundamental law of the universe. You cannot build a robot that spits out every possible infinite loop, because the math says it's impossible to list them all.

The "Speed Bump" Problem

Next, they asked: What if we need the generator to be fast? In the real world, you can't wait a million years for a test case. You need results in seconds.

The researchers discovered a surprising twist: Being able to check if something is valid is not the same as being able to make something valid.

The SAT Solver Example: Imagine a puzzle where you have to find a specific combination of switches to turn on a light. Checking if a combination works is hard (it's "NP-complete"). But the researchers showed that you can build a fast robot that generates these working combinations. It works by "planting a witness": the robot secretly picks a winning combination first, then builds the puzzle around it.
The Hash Collision Trap: However, they also proved that for some problems, even if checking the answer is easy, making the answer might be impossible to do quickly. They looked at "hash collisions" (finding two different inputs that produce the same digital fingerprint). Checking if two fingerprints match is super fast. But finding a pair that matches? If you could build a fast robot to do this, you would break the security of almost all modern encryption.
- The Verdict: Unless the world of cryptography is broken, there are problems where checking is easy, but generating is hard. You can't just wish for a fast generator; sometimes, the math simply won't allow it.

The "Memory" Constraint (Fuzzing and Feedback)

Many modern testing tools, like "fuzzers," don't just spit out random data; they remember what they tried before. If a test crashes the program, the fuzzer remembers that and tries to tweak the input to crash it again. This is like a detective who learns from every clue.

The researchers modeled this as a generator with a limited amount of memory (space). They found that even with this "memory" and feedback loop, the generator is still capped.

The Limit: If the generator has a polynomial amount of memory (which covers almost all practical tools), it can only generate things that belong to a class called PSPACE.
The Reality Check: This means that even the smartest, most memory-hungry fuzzing tools cannot generate inputs for problems that are "EXPTIME-complete" (problems that take exponential time to solve). If a problem is too complex to be solved by a PSPACE machine, no amount of feedback or memory will help a generator create test cases for it.

The "Composability" Myth

Finally, they tackled a dream of software engineers: Can we build a "Lego set" of generators?
Imagine having a tool where you say, "I want a generator for A AND B," or "I want a generator for NOT A," and the tool automatically combines them into a new, fast generator.

The paper delivers a hard NO to this dream, under standard assumptions.

The Rule: You cannot automatically combine generators using "AND" (conjunction) or "NOT" (negation) and guarantee they will still be fast.
Why? If you could do this, you could solve problems that are currently believed to be impossible to solve quickly.
The Exception: You can do this for very simple, restricted types of logic (like "linear Datalog" or "NL" problems), but as soon as you add complex "ANDs" or "NOTs," the magic breaks. If you want to combine complex rules, you have to give up on speed guarantees or accept that your generator might just "try and fail" (rejection sampling) until it gets lucky.

The Big Picture

The paper concludes that generating data is a distinct, often harder challenge than deciding if data is valid.

What is proven: They proved that the set of all generable things is exactly the set of recursively enumerable things. They proved that fast generators for certain hard problems exist (like SAT) but not for others (like hash collisions, assuming crypto is safe). They proved that feedback-driven tools are bounded by PSPACE.
What is ruled out: They ruled out the possibility of a universal, fast, compositional library that can handle any logical combination of rules. They ruled out the idea that "easy to check" always means "easy to generate."

In short, if you are building a testing robot, you can't just wish for it to be fast and smart. The math has drawn a line in the sand: some things are impossible to generate, some are impossible to generate quickly, and some things you can't mix and match without breaking the speed. But now, we finally know exactly where those lines are.

Technical Summary: Complexity Theory of Randomised Testing

Problem Statement

Randomised testing, particularly Property-Based Testing (PBT), relies heavily on generators to produce inputs for a System Under Test (SUT). Despite extensive practical development, the theoretical foundations of these generators remain underexplored. Specifically, the fundamental question of what it means for a set of inputs to be "generable"—both in terms of existence and efficiency—has not been rigorously answered. Practitioners often face uncertainty regarding the limits of generator expressivity: what languages can be generated at all, and which can be generated efficiently? Furthermore, there is a lack of formal understanding regarding the relationship between the complexity of deciding membership in a language (decision complexity) and the complexity of generating instances of that language (generation complexity).

Methodology

The authors establish a complexity-theoretic framework by modelling randomised generators as Turing machine transducers.

Formal Model: A generator is defined as a deterministic Turing machine with three tapes: a read-once-only input tape (consuming random bits), a working tape, and a write-once-only output tape.
Randomness: Randomness is modelled as an explicit input bitstring (an infinite stream of fair coin flips). A generator is considered "eventually productive" if it produces an output for almost all infinite bitstreams (probability 1).
Resource Constraints: The authors introduce families of generators indexed by the size of the output (e.g., string length $n$ $n$ ). They define complexity classes based on time and space bounds relative to this output size:
- GEN: All generable languages (unconstrained).
- PG: Polynomial-time generable languages.
- EPG: Expected polynomial-time generable languages.
- LG: Log-space generable languages.
- PSPACEG: Polynomial-space generable languages.
Correlated Generation: To model feedback-driven techniques like coverage-guided fuzzing and concolic execution, the authors extend the model to include oracle access to the SUT, analyzing space-bounded generation where previous outputs influence future ones.

Key Contributions and Results

1. Expressivity Bounds (Unconstrained Generation)

The paper establishes that the set of generable languages coincides exactly with the Recursively Enumerable (RE) languages.

Theorem 3.1: $GEN = RE$.
Implication: A language is generable if and only if it is RE. Consequently, languages outside RE (such as the set of non-terminating programs, by Rice's Theorem) cannot be generated by any algorithm. This implies that properties with non-RE preconditions (e.g., testing a compiler on all non-terminating programs) cannot be fully tested via randomised testing; any generator must necessarily sample from a strict subset, testing a weaker property.

2. Efficient Generation (Polynomial Time)

The authors investigate the class PG (polynomial-time generable languages) and its relationship to classical complexity classes.

Containment in NP: $PG \subseteq NP$ . Efficient generation requires the precondition to be in NP; if a precondition is PSPACE-hard or coNP-hard (e.g., quantified boolean formulas or unsatisfiable formulas), no fully general polynomial-time generator exists.
Strict Separation from P: Under standard cryptographic assumptions (specifically the existence of collision-resistant hash functions), there are languages in P that are not in PG.
- Theorem 5.1: If collision-resistant hash functions exist, then $P \not\subseteq PG$ .
- Implication: Easy decision complexity is neither necessary nor sufficient for efficient generation. One can efficiently decide if a hash collision exists (in P), but cannot efficiently generate one (unless hash functions are broken).
NP-Completeness: Despite the separation from P, PG contains NP-complete problems. For example, the authors show that CNF-SAT is in PG by constructing a generator that samples a random assignment and builds a formula satisfied by that assignment (witness planting).

3. Characterisation of Efficient Generability

The paper provides a structural characterisation of PG languages.

Theorem 7.1: A language $L$ $L$ is in PG if and only if it admits a certificate scheme. This means there exists a polynomial-time verifier $V$ $V$ such that one can:
1. Sample a random certificate $c$ .
2. Efficiently reconstruct a random instance $w$ from $c$ such that $V(w, c)$ accepts.
Significance: This formalises "witness planting" (generating an instance around a known solution) as the fundamental mechanism for all efficient generators. It implies that any efficient generator for an NP language essentially operates by sampling a witness and reconstructing the problem instance.

4. Space-Bounded Generation and Feedback

The authors analyse generators that produce correlated samples, modelling techniques like concolic execution and coverage-guided fuzzing.

Theorem 6.1: $PSPACEG = PSPACE$.
Implication: Feedback-driven generation techniques, even with oracle access to the SUT, are bounded by PSPACE. If the SUT itself does not solve PSPACE-complete problems, then feedback-driven techniques cannot generate inputs for EXPTIME-complete sets. This limits the theoretical power of coverage-guided fuzzing for certain high-complexity problems.

5. Limitations of Compositional Libraries

The paper addresses the design of PBT libraries that aim to compose generators from logical predicates.

Theorem 7.2: Under standard assumptions ( $NP \neq coNP$ and existence of collision-resistant hash functions), the class PG is not closed under complementation or intersection.
Implication: No library can compositionally map logical predicates involving negation ( $\neg$ ) or conjunction ( $\land$ ) to polynomial-time generators while preserving efficiency guarantees. Designers must either restrict the predicate language (e.g., to NL or linear Datalog, which are closed under these operations) or rely on rejection sampling, which may be inefficient.

Significance

The paper claims to provide the first complexity-theoretic foundations for randomised testing generators. Its significance lies in:

Clarifying Limits: It rigorously defines what can and cannot be generated, distinguishing between decision complexity and generation complexity.
Validating and Refuting Intuitions: It confirms that "witness planting" is the necessary structure for efficient generation and proves that easy-to-decide properties (like hash collisions) can be hard to generate.
Guiding Tool Design: It offers negative results for the design of compositional testing libraries, showing that general compositionality with efficiency guarantees is impossible for standard logical operators.
Broad Applicability: While motivated by software testing, the framework applies to any field requiring randomised generation from constrained sets, such as Markov Chain Monte Carlo (MCMC) and chemical space generation.

The authors conclude that their framework allows for a rigorous analysis of testing campaigns, moving beyond empirical heuristics to formal guarantees regarding the feasibility and efficiency of input generation.