[Computational Complexity] Complexity Report from DNA 15
- Guest post by Aaron Sterling
I attended DNA 15, the 15th International Meeting on DNA Computing and Molecular Programming, held June 8-11, 2009, at the University of Arkansas. The co-chairs of the organizing committee were Rusell Deaton and Jin-Woo Kim, who I thought did a great job. The research presented, and the backgrounds of the attendees, were diverse from experimental nanochemistry to theoretical computer science. I'll highlight a few elements of the program that had TCS and complexity flavor.
Jim Aspnes and Kenichi Morita gave TCS plenary talks. Aspnes introduced the audience to the computational theory of “population protocols” (see here for a survey) a theory of computation over a large network of agents who each possess very limited computational power. This theory can model ad hoc wireless networks, and (potentially) smart molecules interacting in solution. Morita surveyed results on reversible cellular automata and presented animations that showed the inner workings of several such devices. A reversible computation device is one in which each noninitial configuration has exactly one preceding configuration. Many models of natural computing are reversible models.
NP-completeness of the Direct Energy Barrier Problem Without Pseudoknots, due to Manuch et al., was presented by Anne Condon. The Energy Barrier Problem is decision problem about molecular folding. Given a structure in some initial configuration, does there exist a pathway through subsequent configurations to a final configuration, such that the step from each configuration to the next requires at most energy k, for some fixed k. The paper reduces a simplified version of the Energy Barrier Problem to 3-Partition, a known NP-complete problem.
Several papers discussed the theory and practice of building DNA-based circuits. I would like to focus on Signal Propagation and Propagation Delays in Molecular Circuits by Seelig and Soloveichik, as it puts forth the thesis that circuit depth is not the correct measure of time complexity for chemical circuits (in contrast to electronic circuits, or classical circuit complexity). They present a theoretical model to capture something that has been observed in the lab: when there are just a few molecules of a certain species in solution, the reactions that depend on them will be slow, because the species will interact with low probability, since contact with it is so rare. As a result, stepping through a circuit is not a linear process. Approach to completion of a circuit becomes increasingly slow the deeper the circuit is, because the later layers require the output of all the earlier layers. 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. The drawback to this is leakage: if a chemical species is not fully consumed at an earlier stage, its presence can build exponentially at later stages, leading to the circuit providing incorrect answers. All in all, an intriguing model that raises a lot of questions.
DNA 16 will take place in Hong Kong, and DNA 17 will be organized by Erik Winfree at CalTech. I'm looking forward to them both!
Posted By Lance to Computational Complexity at 6/25/2009 06:12:00 AM