A quantified Boolean formula (QBF) is a satisfiability problem with layers of "there exists" and "for all" stacked on top of each other — a two-player game in which one side picks values to make a logical specification hold and an adversary picks values to break it. Competitive transcriptional repression is biology's own zero-sum contest of much the same shape: repressors shut genes off not by chemically destroying anything, but by physically occupying the DNA landing pads that activators need, masking the protein surfaces activators use, or blocking the RNA polymerase from assembling at a promoter. When a repressor and an activator compete for the same or overlapping binding sites — as XTR1 does against the activator XYR1 at the xylanase promoter in Trichoderma reesei (A novel transcriptional repressor specifically regulates xylanase gene 1 in Trichoderma reesei, which showed the two proteins vie for identical promoter motifs) — the two can never be bound at once, so entire regions of the circuit's state space are physically unreachable.
This proposal's claim is that those unreachable states are exactly the "don't cares" that quantified exact synthesis is built to exploit. In electronic design, Reichl, Slivovsky, and Szeider showed that a solver asked "does there exist a smaller subcircuit that, for all input combinations, produces the same global output?" achieves far deeper reduction than strict equivalence checking precisely because it reasons about unreachable internal states without enumerating them (Circuit Minimization with QBF-Based Exact Synthesis). We port that idea to synthetic gene circuits, where the don't cares come not from logical unreachability but from steric exclusion at shared promoter sites. And because QBF proof complexity tells us that quantifier order is what makes these problems hard — universal literals pile up in clauses when an existential variable must wait for preceding universal ones (Are Short Proofs Narrow? QBF Resolution is not Simple.) — the same encoding gives a structured family of formulas in which the prefix order is literally the order of binding sites along the DNA, and the known width blowup corresponds to a molecular traffic jam. The biology is the application; the proof complexity is both the obstacle and the diagnostic.
Core Claim
Synthetic gene circuits are small — a logic gate or toggle switch is a handful of promoters and transcription factors — which places them squarely inside the ten-to-fifteen-element window where QBF exact synthesis is tractable and where it fails for large silicon designs (Circuit Minimization with QBF-Based Exact Synthesis). Within that window, we claim three things. First, competitive repression can be encoded as a three-level quantified game whose inner physics prunes the search space:
$$\exists\, \text{wiring } W \;\; \forall\, \text{input signals } u \;\; \exists\, \text{occupancy } \sigma:\;\; \mathrm{Steric}(\sigma) \,\wedge\, \mathrm{Out}(W,\sigma)=\mathrm{Spec}(u),$$
where $W$ is the circuit's part list and layout, $u$ ranges over environmental and input signals chosen adversarially, $\sigma$ is a promoter-occupancy configuration, and $\mathrm{Steric}(\sigma)$ forbids two competitors from occupying overlapping sites. Minimization asks for the smallest $W$ satisfying the game. The $\mathrm{Steric}$ predicate is the source of implicit don't cares: any behavior spec that only depends on reachable $\sigma$ can be realized by a strictly smaller circuit than equivalence-based synthesis will find. Second, fixing the quantifier prefix to follow the DNA coordinate — universal occupancy choices ordered by position, existential gene responses after them — yields formula families whose proof complexity is governed by how much the sliding competitors' search windows overlap, giving a physically parameterized instance of the universal-literal accumulation phenomenon. Third, the resulting formulas form a genuine empirical testbed for the field's open "master key" problem: finding a structural metric that actually predicts proof length in general Q-resolution, where both clause width and existential width are known to fail (Are Short Proofs Narrow? QBF Resolution is not Simple.).
Research Program
The encoding strand builds a compiler from a promoter-level circuit description to QBF. Mutual-exclusion constraints are taken directly from the documented mechanisms of competitive repression: same-motif occupancy races as in the XTR1/XYR1 system (A novel transcriptional repressor specifically regulates xylanase gene 1 in Trichoderma reesei), RNAP-blocking at core promoter elements as in the sigma-factor discriminator of Edwardsiella (Critical role for a promoter discriminator in RpoS control of virulence in Edwardsiella piscicida), and one-dimensional sliding interference, in which transcription factors searching along the DNA act as mutual roadblocks, as modeled from the 6,500-promoter FACS-seq library of Sharon et al. (Probing the effect of promoters on noise in gene expression using thousands of designed sequences). The compiler emits both the synthesis formula above and its fixed-wiring decision variants.
The theory strand defines roadblock families $\mathrm{RB}(n,k)$: a linear promoter of $n$ sites contested by competitors whose one-dimensional search windows overlap in $k$ consecutive positions, with the quantifier prefix ordered by site position. The program is to prove that overlapping regimes ($k \geq 2$) force linear clause width in Q-resolution despite polynomial proof size — reproducing, with a physical knob, the behavior Beyersdorff et al. established for QParity and modified Janota–Marques-Silva formulas (Are Short Proofs Narrow? QBF Resolution is not Simple.) — and to propose an overlap width, counting universal literals whose sliding domains intersect a clause's existential support, as a candidate master-key metric for this family. We will also test whether the formula gauge of Böhm et al., which measures how strictly solver branching respects prefix dependencies (Lower Bounds for QCDCL via Formula Gauge), predicts solver cost on $\mathrm{RB}(n,k)$, since practical QCDCL and Q-resolution are known to be exponentially incomparable (Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution). A caution we take seriously: the circuit-to-proof lower-bound machinery of Beyersdorff, Bonacina, and colleagues currently applies only to $\exists\forall\exists$ prefixes (Lower Bounds: From Circuits to QBF Proof Systems), while our encodings naturally produce longer alternations, so we cannot import their lower bounds wholesale; our families are instead candidates for extending that theory.
The engineering strand wraps the encoding in a peephole loop, following the windowed-replacement architecture of Reichl et al. (Circuit Minimization with QBF-Based Exact Synthesis) and reusing infrastructure patterns from the available PruneX codebase (MIRALab-USTC/AI4LogicSynthesis-PruneX). The validation strand confronts the proposal's main physical risk head-on: Sharon et al. found that packing more binding sites for sliding factors increases expression noise — promoters with the same mean expression can vary in noise by more than an order of magnitude, with a predictive model reaching $R^2 = 0.82$ (Probing the effect of promoters on noise in gene expression using thousands of designed sequences). Designs that exploit competition to shrink part count may therefore inherit traffic-jam noise. Every synthesized circuit is simulated with the piecewise-deterministic Markov process framework of Hufton et al. — which treats promoter switching as stochastic jumps and protein levels as continuous variables, and delivered a 1,000-fold speedup over Gillespie simulation (A stochastic and dynamical view of pluripotency in mouse embryonic stem cells) — using noise parameters calibrated against the Sharon et al. measurements, and accepted only if mean output stays in spec and noise stays below the top decile of that library's observed dynamic range.
Baselines
The naive reference point is doing nothing: the circuits as delivered by the SynBio-Reason benchmark, whose 4,753 instances span six canonical architectures including logic gates and toggle switches (GenCircuit-RL: Reinforcement Learning from Hierarchical Verification for Genetic Circuit Design). Their part counts and functional pass rates define zero reduction and the correctness floor; any re-synthesized circuit must first match their pass rate before a part-count comparison means anything.
The strongest existing competitor is GenCircuit-RL itself, which trains an autoregressive model with reinforcement learning against a five-level verification schema and reports a 14–16 percentage point improvement in task success rate over the same model trained with binary rewards on SynBio-Reason (GenCircuit-RL: Reinforcement Learning from Hierarchical Verification for Genetic Circuit Design). It is the strongest because it is the only published system that both scales across this benchmark and checks biological function at the circuit level. The fair comparison runs both on the identical logic-gate and toggle-switch subsets with the same part library, the same five-level verification as the referee, and equal compute: GenCircuit-RL gets its full tuning and curriculum budget, while our deterministic method spends its budget on window selection and solver timeouts. Beating it means producing circuits with a strictly smaller mean part count at equal or higher functional pass rate — and, unlike the RL system, handing back a machine-checkable correctness certificate for every circuit. Because GenCircuit-RL generates rather than minimizes, we additionally run our tool as a post-processing pass on its outputs, which is the most direct like-for-like test.
The key-ingredient ablation is strict-equivalence re-synthesis: the identical solver, window scheme, and timeout budget, with the $\mathrm{Steric}$ predicate removed so the formula demands exact equivalence and the competition-derived don't cares vanish. This is the comparison that isolates the proposal's core mechanism, and it has a calibrated precedent: on silicon benchmarks, Reichl et al. report an average gate reduction of 24.3% when quantified global context and implicit don't cares are used, against 8.4% for strict local equivalence (Circuit Minimization with QBF-Based Exact Synthesis). If promoter benchmarks show no gap between the two settings, the claim that competitive exclusion is a useful source of don't cares is falsified.
Why not just…?
Why not just use SMT model checking, as Giacobbe et al. did for gene networks? Their GenCons method synthesizes the full space of weight parameters under which a Boolean gene network satisfies a temporal-logic property, using the Z3 solver, and beat brute-force simulation by up to three times on networks like the mutual-inhibition switch once more than $10^5$ samples were needed (Model Checking Gene Regulatory Networks). It is the right tool for the question it asks, and we use it as a post-hoc checker on our outputs. But it cannot ask our question: its constraints are purely existential, so a universal condition — "for every adversarial input regime there exists a correct internal configuration" — must be unrolled into exponentially many solver calls, and its model of regulation as a weighted linear sum has no place for steric exclusion, which is where our don't cares come from. The experiment that settles it is the ablation above: the value of the universal layer is precisely the measured gap between the quantified and existential variants on the same benchmarks.
Why not just simulate the dynamics? The piecewise-deterministic framework of Hufton et al. is fast — a 1,000-fold speedup over Gillespie simulation on the twelve-factor mouse embryonic stem cell network (A stochastic and dynamical view of pluripotency in mouse embryonic stem cells) — and it captures noise that any Boolean encoding flattens. But it is descriptive: it evaluates one parameterized design at a time, cannot search the space of wirings, and cannot certify worst-case behavior over all input regimes; Giacobbe et al. document exactly this poor scalability and lack of completeness for simulation-based analysis (Model Checking Gene Regulatory Networks). In this proposal simulation is the validator, not the synthesizer, and experiment E4 below is designed so that if simulation shows our minimized circuits failing their noise spec, the proposal fails with them.
Why not just train a generative model like GenCircuit-RL? This is a real threat and we do not argue it away: the RL system scales to 4,753 circuits where exact QBF synthesis never will, and its reported 14–16 percentage point gain is on the very benchmark we use (GenCircuit-RL: Reinforcement Learning from Hierarchical Verification for Genetic Circuit Design). Its weaknesses are equally documented: performance on de novo tasks collapses into degenerate solutions without carefully tuned curricula, it treats parts as modular blocks with no representation of promoter competition or kinetic noise, and it offers no correctness proof. The same incompleteness pattern appears in learned pruning for silicon synthesis, where ELF's classifier deliberately trades recall of 93–95% for speed and silently misses valid optimizations (ELF: Efficient Logic Synthesis by Pruning Redundancy in Refactoring). Our answer is scope, not competition: exact synthesis runs only on peephole windows of ten to fifteen parts, inside the tractability boundary established by Reichl et al. (Circuit Minimization with QBF-Based Exact Synthesis), and experiment E3 explicitly measures whether the QBF pass adds verified part reductions on top of GenCircuit-RL outputs. If it does not, the honest conclusion is that the two methods are not complementary and our claim shrinks to the theory strand.
Proposed Experiments and Decisive Checks
The first experiment is an engineering sanity check: run our solver pipeline on the EPFL Combinational Benchmark Suite and the IWLS '22 contest set, the benchmarks on which Reichl et al. reported their 24.3% versus 8.4% reductions and found the smallest known implementations for the int-to-float converter and coding-cavlc designs (Circuit Minimization with QBF-Based Exact Synthesis). We do not need to match those numbers exactly; we need the pipeline to reproduce the qualitative gap between quantified and strict-equivalence modes before trusting it on biology.
The second experiment is the proof-complexity study. We generate $\mathrm{RB}(n,k)$ grids varying promoter length and overlap, then measure QCDCL solve times and refutation widths, testing whether existential width, the formula gauge (Lower Bounds for QCDCL via Formula Gauge), and our proposed overlap width each predict solver cost, and whether solver configurations that relax prefix order gain where the gauge predicts they should — the behavior Böhm et al. used to prove QCDCL and Q-resolution incomparable (Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution). No reported result exists on Lacuna for QBF solver runtimes on any biology-derived formula family — the relevant literature reports only asymptotic bounds (Are Short Proofs Narrow? QBF Resolution is not Simple., Lower Bounds: From Circuits to QBF Proof Systems) — so any strong correlation here is a new empirical result.
The third experiment is the synthesis evaluation on the logic-gate and toggle-switch subsets of SynBio-Reason (GenCircuit-RL: Reinforcement Learning from Hierarchical Verification for Genetic Circuit Design), reporting part-count reduction and functional pass rate under the benchmark's own five-level verification for four conditions: untouched originals, strict-equivalence re-synthesis, full roadblock-aware synthesis, and GenCircuit-RL outputs re-minimized under both settings. The fourth experiment is the noise audit: piecewise-deterministic simulation of every synthesized circuit with Sharon-calibrated noise parameters (A stochastic and dynamical view of pluripotency in mouse embryonic stem cells, Probing the effect of promoters on noise in gene expression using thousands of designed sequences), accepting designs only if mean expression and noise stay within the stated spec across perturbed input regimes.
Three checks decide the proposal. If the ablation shows no reduction gap between quantified and strict-equivalence modes on promoter benchmarks — unlike the 24.3% versus 8.4% gap on silicon — then competitive exclusion is not a usable source of don't cares and the core claim is wrong. If none of the width metrics, including overlap width, tracks solver cost on $\mathrm{RB}(n,k)$, the theory strand contributes nothing to the master-key problem. And if the noise audit rejects a substantial fraction of competition-exploiting designs, the practical claim must be withdrawn even if the reductions stand, because a smaller circuit that only works in the deterministic abstraction is not a circuit anyone should build.
References
- A novel transcriptional repressor specifically regulates xylanase gene 1 in Trichoderma reesei
- Circuit Minimization with QBF-Based Exact Synthesis
- Are Short Proofs Narrow? QBF Resolution is not Simple.
- Critical role for a promoter discriminator in RpoS control of virulence in Edwardsiella piscicida
- Probing the effect of promoters on noise in gene expression using thousands of designed sequences
- Lower Bounds for QCDCL via Formula Gauge
- Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
- Lower Bounds: From Circuits to QBF Proof Systems
- A stochastic and dynamical view of pluripotency in mouse embryonic stem cells
- GenCircuit-RL: Reinforcement Learning from Hierarchical Verification for Genetic Circuit Design
- Model Checking Gene Regulatory Networks
- ELF: Efficient Logic Synthesis by Pruning Redundancy in Refactoring