Editing Open Problems (section)

===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$?"