Editing Open Problems (section)

= Reachability in real-valued CRNs =

===Context===
Assume the CRN has $k$ species, so that a state of the CRN is a vector $\vec{c} \in \mathbb{R}^k_{\geq 0}$.

In the discrete model of CRNs, there is a clear and incontestable definition of what it means for one state $\vec{d} \in \mathbb{N}^k$ to be ''reachable'' from another state $\vec{c} \in \mathbb{N}^k$: there is a finite sequence of states $\vec{c} = \vec{c}_0,\vec{c}_1,\ldots,\vec{c}_{n-1},\vec{c}_n = \vec{d}$ such that each $\vec{c}_i$ results from applying a single reaction to state $\vec{c}_{i-1}$ (and that reaction is applicable: all the reactants are present in sufficient count to execute the reaction). The definition of reachability forms the basis for several results and other definitions in discrete CRNs. In particular, it captures the notion that it is ''possible'' for the CRN to go from state $\vec{c}$ to state $\vec{d}$, even though it may be unlikely to do so.

In the real-valued model, it is not clear what it means for one state to be reachable from another. The real-valued model is often called the "deterministic" model, but this is typically when mass-action kinetics are used (which, being described by differential equations with a unique solution, are inherently deterministic). However, we would still like to describe what it might mean to claim that the CRN ''could'' (if reactions happened at some rates other than that described by mass-action kinetics) reach from state $\vec{c}$ to state $\vec{d}$, while obeying the intuitive constraint that it should be impossible for some reaction to occur with positive rate in any state in which some of its reactants have concentration 0. Another goal is that it should contain known rate laws as special cases: if some rate law says that the CRN will reach from state $\vec{c}$ to state $\vec{d}$, then the generalized definition should agree that $\vec{d}$ is reachable from $\vec{c}$.

Here is one reasonable looking definition. We say that $\vec{d}$ is ''curve-reachable'' from $\vec{c}$ if there is a continuous curve in concentration space (a continuous function $\rho:[0,1] \to \mathbb{R}^k_{\geq 0}$) such that 
# $\rho$ is differentiable (i.e., there is a well-defined tangent vector at all points along the curve).
# For each $t \in [0,1]$ (which we refer to as "time" $t$, although this termininology is taken from the vocabulary of parameterized curves and is not intended to describe "real time", as this is not a kinetic model), $\rho'(t)$ (the derivative of $\rho$ at time $t$, which is the tangent vector at time $t$) is expressible as $\rho'(t) = \sum_{i=1}^\ell f_i(t) \vec{v}_i$, where $\vec{v}_i$ is the $i$'t reaction vector (the product vector minus the reactant vector for the $i$'th reaction), and $f_i(t) \geq 0$ is a nonnegative real number (the "instantaneous flux" through the $i$'th reaction at time $t$). In other words, at every point along the curve, the motion in the direction of the curve is interpretable as "run the reactions at some nonnegative rates".
# If $f_i(t) > 0$, then for all reactants $X$ of the $i$'th reaction, $\rho(t)(X) > 0$. In other words, if the flux through the $i$'th reaction is strictly positive at time $t$, then all reactants of that reaction must actually be present at time $t$.

This definition is appealing because all known rate laws, such as mass-action, Michaelis-Menten, and Hill function kinetics, trace out curves that obey the stated properties. However, the definition is not reasonable, as the following example shows.

Suppose we have a single species $X$, an empty initial state $\emptyset$, and the reaction $X \to 2X$. Intuitively, the reaction should mean that we need some $X$ to produce more $X$, and since we start with no $X$, there should be no states reachable from $\emptyset$ except $\emptyset$ itself. However, consider the curve $\rho:[0,1] \to \mathbb{R}$ defined by $\rho(t) = t^2$. It actually obeys all three properties, yet it testifies that the state with concentration 1 of $X$ is curve-reachable from $\emptyset$.

We can state more precisely what is wrong with the definition. Define a ''siphon'' to be a subset $\Omega$ of species such that every reaction with an element of $\Omega$ as a product also has an element of $\Omega$ (possibly a different one) as a reactant. Intuitively, "to produce something in $\Omega$ you need something in $\Omega$". It may seem "obvious" that this is equivalent to stating that "the absence of $\Omega$ is forward-invariant": if state $\vec{c}$ has concentration 0 of all species in $\Omega$, then every state $\vec{d}$ reachable from $\vec{c}$ also has concentration 0 of all species in $\Omega$. However, in the case of mass-action reachability, this implication is a deep theorem that requires a sophisticated proof. And in the case of curve-reachability, it is false. In fact, it is reasonable to say that the failure to enforce the "forward-invariant absence of siphons" is precisely what is wrong with the definition of curve-reachability. Property 3 was intended to enforce this condition, but it failed.

=== Problem statement ===
Give a definition of reachability in real-valued CRNs based on continuous curves in $\mathbb{R}^k$, such that curves traced out by all known rate laws are special cases of it, and such that it respects the forward-invariant absence of siphons, as well as the intuitive idea that "motion along the curve should be interpretable as each reaction happening at some nonegative rate".

There is a definition of reachability in <ref name="CDS2014">Ho-Lin Chen, David Doty, David Soloveichik (2014). Rate-independent computation with continuous chemical reaction networks. Innovations in Theoretical Computer Science, 2014</ref>. It is based on finite numbers of straight-line segments. It obeys the "forward-invariant absence of siphons" constraint, and it also enforces that each straight line is interpretable as running some reactions. However, finite unions of straight line segments cannot describe smooth curves such as those produced by mass-action kinetics. We did prove that this notion of reachability is more general than mass-action: if $\vec{d}$ is mass-action reachable from $\vec{c}$ (under some setting of rate constants, and $\vec{d}$ could be reached either in finite time, or in the limit as time goes to infinity), then $\vec{d}$ is reachable from $\vec{c}$ via a finite number of straight-line segments under our definition. But it would be more elegant if the actual curves used in the definition had the curves traced out by mass-action and other rate laws as special cases (which would immediately imply that reachability under those rate laws implies reachability under the more generalized notion).

=== Interested Participants ===

* [[User:Doty | Dave Doty ]]
* [[User:dsolov | David Soloveichik ]]
* [[Niranjan Srinivas ]]