skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Computing Threshold Circuits with Bimolecular Void Reactions in Step Chemical Reaction Networks
Step Chemical Reaction Networks (step CRNs) are an augmentation of the Chemical Reaction Network (CRN) model where additional species may be introduced to the system in a sequence of “steps.” We study step CRN systems using a weak subset of reaction rules, void rules, in which molecular species can only be deleted. We demonstrate that step CRNs with only void rules of size (2,0) can simulate threshold formulas (TFs) under linear resources. These limited systems can also simulate threshold circuits (TCs) by modifying the volume of the system to be exponential. We then prove a matching exponential lower bound on the required volume for simulating threshold circuits in a step CRN with (2,0)-size rules under a restricted gate-wise simulation, thus showing our construction is optimal for simulating circuits in this way.  more » « less
Award ID(s):
2329918
PAR ID:
10562738
Author(s) / Creator(s):
; ; ; ; ; ; ;
Publisher / Repository:
Springer Nature
Date Published:
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Schaeffer, Josie; Zhang, Fei (Ed.)
    For general discrete Chemical Reaction Networks (CRNs), the fundamental problem of reachability - the question of whether a target configuration can be produced from a given initial configuration - was recently shown to be Ackermann-complete. However, many open questions remain about which features of the CRN model drive this complexity. We study a restricted class of CRNs with void rules, reactions that only decrease species counts. We further examine this regime in the motivated model of step CRNs, which allow additional species to be introduced in discrete stages. With and without steps, we characterize the complexity of the reachability problem for CRNs with void rules. We show that, without steps, reachability remains polynomial-time solvable for bimolecular systems but becomes NP-complete for larger reactions. Conversely, with just a single step, reachability becomes NP-complete even for bimolecular systems. Our results provide a nearly complete classification of void-rule reachability problems into tractable and intractable cases, with only a single exception. 
    more » « less
  2. ; ; ; ; ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Meeks, Kitty; Scheideler, Christian (Ed.)
    For general discrete Chemical Reaction Networks (CRNs), the fundamental problem of reachability - the question of whether a target configuration can be produced from a given initial configuration - was recently shown to be Ackermann-complete. However, many open questions remain about which features of the CRN model drive this complexity. We study a restricted class of CRNs with void rules, reactions that only decrease species counts. We further examine this regime in the motivated model of step CRNs, which allow additional species to be introduced in discrete stages. With and without steps, we characterize the complexity of the reachability problem for CRNs with void rules. We show that, without steps, reachability remains polynomial-time solvable for bimolecular systems but becomes NP-complete for larger reactions. Conversely, with just a single step, reachability becomes NP-complete even for bimolecular systems. Beyond what is contained in this brief announcement, we also investigate optimization variants of reachability, provide approximation results for maximizing species deletion, establish ETH-based lower bounds for NP-complete cases, and prove hardness for counting reaction sequences. 
    more » « less
  3. ; ; (, Journal of The Royal Society Interface)
    Models of well-mixed chemical reaction networks (CRNs) have provided a solid foundation for the study of programmable molecular systems, but the importance of spatial organization in such systems has increasingly been recognized. In this paper, we explore an alternative chemical computing model introduced by Qian & Winfree in 2014, the surface CRN, which uses molecules attached to a surface such that each molecule only interacts with its immediate neighbours. Expanding on the constructions in that work, we first demonstrate that surface CRNs can emulate asynchronous and synchronous deterministic cellular automata and implement continuously active Boolean logic circuits. We introduce three new techniques for enforcing synchronization within local regions, each with a different trade-off in spatial and chemical complexity. We also demonstrate that surface CRNs can manufacture complex spatial patterns from simple initial conditions and implement interesting swarm robotic behaviours using simple local rules. Throughout all example constructions of surface CRNs, we highlight the trade-off between the ability to precisely place molecules and the ability to precisely control molecular interactions. Finally, we provide a Python simulator for surface CRNs with an easy-to-use web interface, so that readers may follow along with our examples or create their own surface CRN designs. 
    more » « less
  4. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Alistarh, Dan (Ed.)
    Chemical reaction networks (CRNs) model systems where molecules interact according to a finite set of reactions such as A + B → C, representing that if a molecule of A and B collide, they disappear and a molecule of C is produced. CRNs can compute Boolean-valued predicates ϕ:ℕ^d → {0,1} and integer-valued functions f:ℕ^d → ℕ; for instance X₁ + X₂ → Y computes the function min(x₁,x₂), since starting with x_i copies of X_i, eventually min(x₁,x₂) copies of Y are produced. We study the computational power of execution bounded CRNs, in which only a finite number of reactions can occur from the initial configuration (e.g., ruling out reversible reactions such as A ⇌ B). The power and composability of such CRNs depend crucially on some other modeling choices that do not affect the computational power of CRNs with unbounded executions, namely whether an initial leader is present, and whether (for predicates) all species are required to "vote" for the Boolean output. If the CRN starts with an initial leader, and can allow only the leader to vote, then all semilinear predicates and functions can be stably computed in O(n log n) parallel time by execution bounded CRNs. However, if no initial leader is allowed, all species vote, and the CRN is "non-collapsing" (does not shrink from initially large to final O(1) size configurations), then execution bounded CRNs are severely limited, able to compute only eventually constant predicates. A key tool is a characterization of execution bounded CRNs as precisely those with a nonnegative linear potential function that is strictly decreased by every reaction [Czerner et al., 2024]. 
    more » « less
  5. ; ; ; (, Natural Computing)
    Chemical reaction networks (CRNs) are an important tool for molecular programming. This field is rapidly expanding our ability to deploy computer programs into biological systems for various applications. However, CRNs are also difficult to work with due to their massively parallel nature, leading to the need for higher-level languages that allow for more straightforward computation with CRNs. Recently, research has been conducted into various higher-level languages for deterministic CRNs but modeling CRN parallelism, managing error accumulation, and finding natural CRN representations are ongoing challenges. We introduce Reactamole, a higher-level language for deterministic CRNs that utilizes the functional reactive programming (FRP) paradigm to represent CRNs as a reactive dataflow network. Reactamole equates a CRN with a functional reactive program, implementing the key primitives of the FRP paradigm directly as CRNs. The functional nature of Reactamole makes reasoning about molecular programs easier, and its strong static typing allows us to ensure that a CRN is well-formed by virtue of being well-typed. In this paper, we describe the design of Reactamole and how we use CRNs to represent the common datatypes and operations found in FRP. We demonstrate the potential of this functional reactive approach to molecular programming by giving an extended example where a CRN is constructed using FRP to modulate and demodulate an amplitude-modulated signal. We also show how Reactamole can be used to specify abstract CRNs whose structure depends on the reactions and species of its input, allowing users to specify more general CRN behaviors. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email