tag:blogger.com,1999:blog-3722233.post6606991413307862047..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Complexity Report from DNA 15Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-60327377415571419782009-06-26T09:35:41.176-05:002009-06-26T09:35:41.176-05:00One possible fix for this is to catalyze the react...<i>One possible fix for this is to catalyze the reactions in question, so the reactions occur quickly even if there is only a small amount of species present.</i><br /><br />Catalysis is not a fix that can be applied to arbitrary reactions; in particular, the problem of rare collisions that you mention is not fixed by catalyzing that reaction. Consider the bimolecular reaction 2A -> B. Catalyzed, it looks like 2A + C -> B + C. Even with lots of C's, after all but two A's have reacted, the two lone A's need to find their way together to react, which will take at least as long with a catalyst as without.<br /><br />What Soloveichik did with his earlier paper with Winfree, Cook, and Bruck (Computation with Finite Stochastic Chemical Reaction Networks, which showed such networks constitute an efficient universal model of computation) was to ensure that all reactions have <i>at most</i> one reactant A that will be present in a small amount; the abundance of the <i>other</i> reactant ensures that the reaction will proceed quickly even when A is down to a single molecule. It does not matter whether the reaction is catalyzed or not. If a <i>unimolecular</i> reaction A -> B is too slow, it can be accelerated through the addition of a catalyst to make a bimolecular reaction: A + C -> B + C, whose the reaction rate is proportional to the amount of C, a quantity easily controlled by the experimenter (and not otherwise affecting the behavior of the system). But this "fix" only works with reactions that are unimolecular to start with, and is fixing a different problem from the rare collision problem.<br /><br />The Seelig/Soloveichik DNA paper broadly classifies reactions as catalytic and non-catalytic, but all the catalytic reactions they study happen also to be bimolecular (counting the catalyst as a reactant). That paper therefore uses the term "catalytic" to mean "bimolecular where one reactant is a catalyst assumed to be present in adundance". But they do not state that the slow speed of non-catalytic bimolecular reactions can be fixed through catalysis, only that "systematic use of [bimolecular] catalysis allows one to build faster circuits with considerably improved asymptotic behaviors". The fact that not all useful non-catalytic reactions are unimolecular makes such systematic use of bimolecular catalysis a non-trivial goal, and is a major focus of the earlier paper and the reason for the incredible depth of its main construction.<br /><br />A general purpose fix for accelerating non-catalytic bimolecular reactions would consitute a breakthrough in the study of stochastic chemical reaction networks. A good example to try out ideas is this: set up a cascade of reactions that will divide the number of A's by two; i.e., it will implement the reaction 2A -> B, but such that by increasing the concentration of one or more catalysts, the reaction can be made to run to completion arbitrarily fast, without the rare collision problem that plagues the final two reacting A's.<br /><br />Dave DotyDavehttps://www.blogger.com/profile/00243750470577898974noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81914502198543129982009-06-25T13:06:02.125-05:002009-06-25T13:06:02.125-05:00Speaking of conferences--is anyone attending CCC09...Speaking of conferences--is anyone attending CCC09 in Paris still looking for a hotel room? If so, want to share a double? Thanks! <br /><br />adrucker at mit dot eduAndy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61870700978150168492009-06-25T10:18:09.422-05:002009-06-25T10:18:09.422-05:00Great post, thanks!Great post, thanks!Anonymousnoreply@blogger.com