Computing Threshold Circuits with Bimolecular Void Reactions in Step Chemical Reaction Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929333435629568 |
|---|---|
| author | Anderson, Rachel Fu, Bin Massie, Aiden Mukhopadhyay, Gourab Salinas, Adrian Schweller, Robert Tomai, Evan Wylie, Tim |
| author_facet | Anderson, Rachel Fu, Bin Massie, Aiden Mukhopadhyay, Gourab Salinas, Adrian Schweller, Robert Tomai, Evan Wylie, Tim |
| contents | 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, \emph{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 \emph{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 \emph{gate-wise} simulation, thus showing our construction is optimal for simulating circuits in this way. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00940 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Threshold Circuits with Bimolecular Void Reactions in Step Chemical Reaction Networks Anderson, Rachel Fu, Bin Massie, Aiden Mukhopadhyay, Gourab Salinas, Adrian Schweller, Robert Tomai, Evan Wylie, Tim Distributed, Parallel, and Cluster Computing Emerging Technologies Multiagent Systems 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, \emph{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 \emph{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 \emph{gate-wise} simulation, thus showing our construction is optimal for simulating circuits in this way. |
| title | Computing Threshold Circuits with Bimolecular Void Reactions in Step Chemical Reaction Networks |
| topic | Distributed, Parallel, and Cluster Computing Emerging Technologies Multiagent Systems |
| url | https://arxiv.org/abs/2405.00940 |