Editing Open Problems (section)

=Computing partial functions=

'''Update:''' After typing all this out, I (Dave Doty) realized that because $\mathbb{N}^k$ is well-quasi-ordered, it is impossible to have an infinite subset of $\mathbb{N}^k$ with all elements being pairwise incomparable. I'm leaving the question in the hopes that some discussion can happen, but I don't know how to formalize a question about the complexity of partial functions with finite domains. (Maybe circuit complexity can help here?)

=== Problem context ===

The standard notion of "stable computation" with CRNs<ref name="CDS2013"/> says that a CRN computes a function $f:\mathbb{N}^k \to \mathbb{N}$ (the concept also makes sense with computing predicates $\phi:\mathbb{N}^k \to \{0,1\}$) if, for every state $\vec{c}$ reachable from the initial state $\vec{x}$, there is a correct "output stable" state $\vec{o}$ reachable from $\vec{c}$. Here, to say that $\vec{o}$ is output stable means that the count of the output species $Y$ cannot change (no reaction producing or consuming $Y$ is possible in $\vec{o}$ or in any state reachable from $\vec{o}$). To say that it is correct means that the count of $Y$ is equal to the intended output $f(\vec{x})$.

One property to observe is that the definition does not capture any notion of the CRN "knowing" when it has computed the correct answer. In the case of functions, the count of $Y$ changes as reactions occur, and eventually it stops changing, but there is no signal that the CRN gives to indicate that the count of $Y$ has stabilized. In the case of predicates, some of the species "vote" for a YES or NO answer, and eventually all the voters are unanimous and correct, but the CRN does not signal that the voters have stabilized.

One could imagine making an additional requirement of the CRN: there is a special molecule $H$ (the "halt" molecule), so that the count of $H$ is initially 0, the CRN is guaranteed eventually to produce $H$, and it is guaranteed that $H$ will not be produced until the answer has stabilized to the correct value. This would enable CRNs to be more easily composed, for example, since a downstream CRN could have its computation triggered by the $H$ molecule of an upstream CRN, to guarantee that they do not execute simultaneously and interfere with each other.

Unfortunately, in the case of total functions, this is impossible for stable computation of nontrivial functions or predicates. In particular, if there are two inputs $\vec{x}_1 < \vec{x}_2$ such that $f(\vec{x}_1) \neq f(\vec{x}_2)$, then there is a sequence of reactions from $\vec{x}_1$ that leads to state $\vec{o}_1$ with $\vec{o}_1(H) > 0$, and since $\vec{x}_1 < \vec{x}_2$, that sequence of reactions is applicable to $\vec{x}_2$, but since $f(\vec{x}_1) \neq f(\vec{x}_2)$ this means it is possible to produce $H$ from $\vec{x}_2$ before the CRN has stabilized to the correct answer $f(\vec{x}_2)$.

However, if $f:\mathbb{N}^k \dashrightarrow \mathbb{N}$ is a partial function, then it is possible for $\mathrm{dom}\ f$ to have all its elements be pairwise incomparable: $(\forall \vec{x}_1, \vec{x}_2 \in \mathrm{dom}\ f)\ \vec{x}_1 \not < \vec{x}_2$. So-called "dual-rail" representations of inputs to Boolean predicates $\phi: \{0,1\}^k \to \{0,1\}$, in which the $i$'th bit is represented in the initial state $\vec{x}$ by two species $1_i$ and $0_i$: $\vec{x}(1_i) = 1$ and $\vec{x}(0_i) = 0$ to represent that the $i$'th bit is 1, and $\vec{x}(1_i) = 0$ and $\vec{x}(0_i) = 1$ to represent that the $i$'th bit is 0. Therefore the set of CRN input states (a vector in $\N^{2k}$ since there are two species to represent each of the $k$ input bits to $\phi$) is pairwise incomparable.

In particular, any Boolean predicate $\phi: \{0,1\}^k \to \{0,1\}$ on a fixed number of input can be stably computed by a CRN, producing molecule $H$ precisely when the output stabilizes. With a standard "indicator" representation (one species $1_i$ to represent the $i$'th input bit), this is impossible for some predicates due to the pairwise comparability of some input states.

===Problem statement===

'''Question 1:''' What is the complexity of partial functions $f:\mathbb{N}^k \dashrightarrow \mathbb{N}$ and predicates $\phi:\mathbb{N}^k \dashrightarrow \{0,1\}$ that can be stably computed by a CRN?

'''Question 2:''' What is the complexity of partial functions $f:\mathbb{N}^k \dashrightarrow \mathbb{N}$ and predicates $\phi:\mathbb{N}^k \dashrightarrow \{0,1\}$ that can be stably computed by a CRN, with the "announcement of halting" convention described previously? (i.e., the CRN produces molecule $H$, but not until the output has stabilized to the correct answer)

In both cases, the CRN is allowed to have undefined behavior on any initial state $\vec{x}$ not in the domain of the function/predicate. This is similar to the computational complexity notion of a promise problem, in which the Turing machine is "promised" to be given only inputs in the domain of the function and is allowed to be undefined -- e.g., not halt -- on other inputs. 

The answer to both questions may depend on the complexity of the domain $\mathrm{dom}\ f$. When the function is total, then the answers for functions and predicates are known to be semilinear functions and semilinear predicates, respectively. Obviously, one can define a partial predicate $\phi:\mathbb{N}^k \dashrightarrow \{0,1\}$ such that $\mathrm{dom}\ \phi$ is very complex but $\phi(\vec{x})=1$ for all $\vec{x} \in \mathrm{dom}\ \phi$. Then the support of $\phi$ (the set $\{\vec{x}|\phi(\vec{x})=1\}$) would also be complex, but intuitively we consider $\phi$ to be very simple since it is partitioning $\mathrm{dom}\ \phi$ in a trivial way.

Intuitively, the questions (in the case of predicates) are asking: "can $\phi$ partition the set $\mathrm{dom}\ \phi$ in a way 'more complex than semilinear' if it is allowed to have undefined behavior on inputs $\vec{x} \not \in \mathrm{dom}\ \phi$?"

=== Interested Participants ===

* [[User:Doty | Dave Doty ]]