Editing Open Problems (section)

= CRNs and circuit complexity =

=== Problem context ===

Consider CRNs in which we give input using the ''binary convention'': to specify the $i$'th bit is 1, have count 1 of $X_i$ in the initial state; otherwise have count 0.

=== Problem overview ===

'''High-level question''': What is the relationship between resource bounds (e.g., number of species/reactions) for CRNs and resource bounds (e.g., number of gates, depth) for Boolean circuits?

'''Precise question (one example):''' Let $n \in \mathbb{N}$ and let $\phi:\{0,1\}^n \to \{0,1\}$ be a Boolean function with $n$ inputs. What is the relationship between the Boolean circuit size $\textrm{size}_{BC}(\phi)$ of $\phi$ (the minimum number of wires in a Boolean circuit with AND, OR, and NOT gates that computes $\phi$) and the "CRN size complexity" $\textrm{size}_{CRN}(\phi)$ of $\phi$? (the minimum number of species/reactions in any CRN that stably computes $\phi$)?

Here, "the CRN stably computes $\phi$" is formally defined in several papers, e.g., <ref name="CDS2013">Ho-Lin Chen, David Doty, David Soloveichik (2013). Deterministic function computation with chemical reaction networks. Natural Computing 2013</ref>. Briefly, it means that there are species $Y$ ("yes") and $N$ ("no"), and starting from the initial state $\vec{x}$, for any state $\vec{c}$ reachable from $\vec{x}$, there is a state $\vec{o}$ reachable from $\vec{c}$ with the following property:

<ul>
<li> If $\phi(\vec{x}) = 1$ then $Y$ is present in $\vec{o}$ and $N$ is absent, and if $\phi(\vec{x}) = 0$ then $N$ is present in $\vec{o}$ and $Y$ is absent, and this remains true in any state reachable from $\vec{o}$.
</ul>

It is clear that $\textrm{size}_{CRN}(\phi) \leq O(\textrm{size}_{BC}(\phi))$. The reverse direction is not clear.

Some preliminary work suggests perhaps $\textrm{size}_{CRN}(\phi)$ could be characterized in terms of the depth of Boolean circuits that compute $\phi$.

=== Interested Participants ===

* [[User:Woods | Damien Woods ]]
* [[User:Doty | Dave Doty ]]
* [[User:Thachuk | Chris Thachuk ]]
* [[User:dsolov | David Soloveichik ]]