Solving Boolean Satisfiability with Allosteric Reaction Networks

Many biological functions rely on the information-processing capabilities of allosteric reaction networks. Yet, it remains unclear how such processing is both enabled and limited by the physical principles governing these systems. In this talk, we present the design of an allosteric reaction network capable of solving Boolean satisfiability (SAT) problems. A SAT problem involves finding a satisfying assignment for a set of $N$ spins subject to $M$ logical constraints. We demonstrate how such a problem can be encoded into a network of reactants that interact solely via equilibrium binding and internal state transitions, reaching a steady-state configuration that corresponds to a solution of a randomly generated 3-SAT instance. We then quantify the success rate of this allosteric solver as a function of the constraint density $M/N$, showing that the network reliably solves weakly to moderately constrained problems, but exhibits failure modes as constraint density increases. These results provide a framework for benchmarking the computational power of allosteric reaction networks and shed light on the fundamental physical limits of biochemical information processing.