Computing Threshold Circuits with Void Reactions in Step Chemical Reaction Networks
We introduce a new model of \emph{step} Chemical Reaction Networks (step CRNs), motivated by the step-wise addition of materials in standard lab procedures. Step CRNs have ordered reactants that transform into products via reaction rules over a series of steps. We study an important subset of weak reaction rules, \emph{void} rules, in which chemical species may only be deleted but never changed. We demonstrate the capabilities of these simple limited systems to simulate threshold circuits and compute functions using various configurations of rule sizes and step constructions, and prove that without steps, void rules are incapable of these computations, which further motivates the step model. Additionally, we prove the coNP-completeness of verifying if a given step CRN computes a function, holding even for $O(1)$ step systems.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the…
LEMMAImplementing Non-Equilibrium Networks with Active Circuits of Duplex Catalysts
DNA strand displacement (DSD) reactions have been used to construct chemical reaction networks in which species act catalytically at the level of the overall stoichiometry of reactions. These effective catalytic reaction…
Neural CRNs: A Natural Implementation of Learning in Chemical Reaction Networks
We present Neural CRNs, an efficient, autonomous, and general-purpose implementation of learning within mass action chemical reaction systems. Unlike prior works, which transliterate discrete neural networks into chemica…
Multi-class ClassificationConstant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
Boolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing ha…
GPUGASP -- A Genetic Algorithm for State Preparation
The efficient preparation of quantum states is an important step in the execution of many quantum algorithms. In the noisy intermediate-scale quantum (NISQ) computing era, this is a significant challenge given quantum re…