We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

q-bio.MN

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Quantitative Biology > Molecular Networks

Title: Computing Threshold Circuits with Void Reactions in Step Chemical Reaction Networks

Abstract: 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.
Subjects: Molecular Networks (q-bio.MN); Emerging Technologies (cs.ET)
Cite as: arXiv:2402.08220 [q-bio.MN]
  (or arXiv:2402.08220v1 [q-bio.MN] for this version)

Submission history

From: Tim Wylie [view email]
[v1] Tue, 13 Feb 2024 05:25:20 GMT (737kb,D)

Link back to: arXiv, form interface, contact.