Editing Open Problems (section)

=Shy molecules=

Some input molecules are shy, they hide in the corner until our CRN computation thinks its done. Then they show up and the CRN should realise it has the wrong answer! For example consider a CRN that is given as input count $n\in\mathbb{N}$ of some input species, and it (erroneously) "reads" only $n-1$ of these and then presents an answer; clearly this answer is premature and possibly incorrect. Another kind of input format where this issue arises is where we give the input to the CRN that computes on binary strings as a positive indicator species for each input symbol that is $1$, e.g. the input string $x = 01001010$ would be presented as count $\geq 1$ of each of the molecules $1_2, 1_5, 1_7$ (these input species are sometimes called ''indicator'' species; they indicate which bits are on). 

Often, to get around this issue we (theoretically or in the lab) provide CRN inputs that contain both positive and negative indicator species (sometimes called  ''dual rail'' inputs). For example,  the input string $x = 01001010$ would be presented as count $\geq 1$ of each of the molecules $0_1, 1_2, 0_3, 0_4, 1_5, 0_6, 1_7, 0_8$. 

'''Vague question:''' What does dual-rail input buy us? What does it cost us? 

For example, suppose we want a strict notion of halting with an answer, which we here call ''announcement stable'' and define as: the CRN outputs by reaching a configuration $c$ with a single answer molecule (one copy $z$ of a molecule from the set $\{\text{yes}, \text{no}\}$) and every configuration reachable from $c$ gives the same answer (contains $z$ and contains zero copies of the other answer molecule). Note that this is stricter than ''output stable'', defined elsewhere on this page. Dual rail inputs seem to more easily facilitate designing of CRNs that are announcement stable.

One can consider this question both in terms of ''families'' of CRNs (see elsewhere on this page) computing a function, or a single CRN, computing a function.

'''Slighly more precise question:''' Consider the class of uniform families of announcement stable, and uniform families of output stable CRNs. What do we pay, in terms of CRN complexity (size, time, etc.), for choosing one output convention over another for solving general classes of problems? 

The following related (and very tentative!) question asks if we can have a CRN model where we are forced to deal with input counts, but where we can be clever and cheaply achieve announcement stability. 

'''Question:''' Consider a family of CRNs, that compute functions on $n$-bit strings, but where the number of input species to the CRN is $< n$, say $O(\log\log n)$, or  $O(\log \log \log\log\log\log n)$ (so we are forced to put "most" of the input into initial counts). Can we handle shy molecules here? More precisely, in this model, can we compute in an ''announcement stable'' way, without paying significant costs? 

'''Another related question:''' By allowing a non-constant, but small ($o(\log log n)$), number of input species, can we compute faster than with a constant number? What is the trade-off between speed of computation and number of input species?



=== Interested Participants ===

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