對輸出視而不見的化學反應網路的速度

Abstract

隨機化學反應網路 (Chemical Reaction Network) 被科學家廣泛的使用來描述分子之間的反應。化學反應網路可以視為一種用來描述分子反應的語言。在化學反應網路中所能夠做到的計算，在現實中的分子也能夠做到。我們假設每個反應的反應率都是1，因為在穩定計算下反應率不會影響到最後的結果。在此篇中我們專注在” 對輸出視而不見的化學反應網路” 上，此種網路可以直接和其他化學反應網路串接且不會有錯誤。 [3] 第一個定義了輸出不會當成某些反應的反應物的化學反應網路為” 對輸出視而不見的化學反應網路”，並且證明了這類網路能夠計算什麼函數，但裡面有一些很慢的反應。我們對這些慢的反應進行改良，並將計算”對輸出視而不見的化學反應網路” 的時間從 O(N^r) 降到 O(NlogN ).

Stochastic Chemical Reaction Networks(CRNs) are widely used to describe how molecules interact with each other by scientists. CRNs can be viewed as a language for describing the reaction between molecules. If the CRNs can compute the function f , so do the molecules in nature. We assume that the rate of each reaction is one because it doesn’t affect the output under the stable computation. In this thesis, we only consider one special type of CRNs called output oblivious CRN. These CRNs can concatenate to other CRNs directly. Chugg et al. [3] first define the CRN whose output species never being a reactant of reaction in CRN as output oblivious CRN. They have characterized all functions f : N^2 → N which can be stably computed by output oblivious CRNs with a leader. However, the CRNs they designed may require an extremely long time to converge to the correct output. We modify the original reactions and reduce the time needed for output oblivious CRN from O(N^r) to O(NlogN ).