Deterministic Function Computation with Chemical Reaction Networks

Details Deterministic Function Computation with Chemical Reaction Networks Deterministic Function Computation with Chemical Reaction Networks

2012-04-18

arxiv.org/abs/1204.4176v1

Computer Science

Computational Complexity

Scientific paper

We study the deterministic computation of functions on tuples of natural numbers by chemical reaction networks (CRNs). CRNs have been shown to be efficiently Turing-universal when allowing for a small probability of error. CRNs that are guaranteed to converge on a correct answer, on the other hand, have been shown to decide only the semilinear predicates. We introduce the notion of function, rather than predicate, computation by representing the output of a function f:N^k --> N^l by a count of some molecular species, i.e., if the CRN starts with n_1,...,n_k molecules of some "input" species X_1,...,X_k, the CRN is guaranteed to converge to having f(n_1,...,n_k) molecules of the "output" species Y_1,...,Y_l. We show that a function f:N^k --> N^l is deterministically computed by a CRN if and only if its graph {(x,y) \in N^k x N^l | f(x) = y} is a semilinear set. Finally, we show that each semilinear function f can be computed on input x in expected time O(polylog |x|).

Affiliated with

Also associated with

No associations

Rating

Deterministic Function Computation with Chemical Reaction Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deterministic Function Computation with Chemical Reaction Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic Function Computation with Chemical Reaction Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-412526