What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they be used to solve instances of NP-complete problems like TSP that von Neumann machines can not solve feasibly in practice?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ I posted a followup question here: cstheory.stackexchange.com/questions/2758/… $\endgroup$– Aaron SterlingNov 7, 2010 at 2:24
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
6
Soundbite answer: DNA computing does not provide a magic wand to solve NP-complete problems, even though some respected researchers in the 1990s thought for a time it might.
The inaugural DNA computing experiment was performed in a laboratory headed by the renowned number theorist Len Adleman. Adleman solved a small Traveling Salesman Problem -- a well-known NP-complete problem, and he and others thought for a while the method might scale up. Adleman describes his approach in this short video, which I find fascinating. The problem they encountered was that to solve a TSP problem of modest size, they would need more DNA than the size of the Earth. They had figured out a way to save time by increasing the amount of work done in parallel, but this did not mean the TSP problem required less than exponential resources to solve. They had only shifted the exponential cost from amount-of-time to amount-of-physical material.
(There's an added question: if you require an exponential amount of machinery to solve a problem, do you automatically require an exponential amount of time, or at least preprocessing, to build the machinery in the first place? I'll leave that issue to one side, though.)
This general problem -- reducing the time a computation requires at the expense of some other resource -- has shown up many times in biologically-inspired models of computing. The Wikipedia page on membrane computing (an abstraction of a biological cell) says that a certain type of membrane system is able to solve NP-complete problems in polynomial time. This works because that system allows for the creation of exponentially-many subobjects inside an overall membrane, in polynomial time. Well... how does an exponential amount of raw material arrive from the outside world an enter through a membrane with constant surface area? Answer: it's not considered. They're not paying for a resource that the computation would otherwise require.
Finally, to respond to Anthony Labarre, who linked to a paper showing AHNEPs can solve NP-complete problems in polynomial time. There's even a paper out showing AHNEPs can solve 3SAT in linear time. AHNEP = Accepting Hybrid Network of Evolutionary Processors. An evolutionary processor is a model inspired by DNA, whose core has a string that at each step can be changed by substitution, deletion, or (importantly) insertion. Further, an arbitrarily large number of strings is available at every node, and at each communication step, all nodes send all their correct strings to all attached nodes. So without time cost, it's possible to transfer exponential amounts of information, and because of the insertion rule, individual strings can become ever larger over the course of the computation, so it's a double whammy.
If you are interested in recent work in biocomputation, by researchers who focus on computations that are real-world practical, I can offer this book review I recently wrote for SIGACT News, which touches briefly on multiple areas.
answered Nov 4, 2010 at 10:52
-
$\begingroup$ @Aaron: Thank you! Now I have to go and read your review. $\endgroup$ Nov 4, 2010 at 11:21
-
$\begingroup$ I couldn't have put it better myself. This is also true for a host of other biological inspired problem solving techniques such as genetic algorithms and protein folding. $\endgroup$– user834Nov 5, 2010 at 3:27
-
6$\begingroup$ @Aaron: You asked "if you require an exponential amount of machinery to solve a problem, do you automatically require an exponential amount of time, or at least preprocessing, to build the machinery in the first place?". The answer is definitely yes. The reason for this is that there is a maximum density possible within a region before you form a black hole (to avoid this you need $r>\frac{2Gm}{c^2}$), which means that the radius of the system must scale proportionately to the mass to avoid this. The computational power scales at most linearly in the mass. (continued below) $\endgroup$ Nov 5, 2010 at 4:39
-
5$\begingroup$ (continued) Thus your exponential amount of machinery has an exponential radius. Since you can't signal faster than light, a signal from one side to another takes an exponentially long time to reach the other side, and so if all the machinery contribute to the answer, it is impossible to solve the problem in less than exponential time. $\endgroup$ Nov 5, 2010 at 4:42
-
$\begingroup$ @Joe: Thank you. :-) Would it be ok for me to quote part of your comments in a followup question? I'm interested in formalisms that capture statements like "The computational power scales at most linearly in the mass." How much Kolmogorov complexity is there per square inch, etc. $\endgroup$ Nov 5, 2010 at 14:50
$\begingroup$
$\endgroup$
4
This very much depends on your model.
In reality DNA computing follows (non-relativistic) physical laws, and so can be simulated on a quantum computer. Thus the best you could hope for is that it could solve BQP-complete problems. However this is actually very unlikely to be true (DNA is quite big, and so coherence isn't really an issue), and so by simulation it is almost certainly P. It is important to note, however, that this is efficiency in terms of the number of atoms used, and frankly atoms are sufficiently cheap that this number is astronomical making practical simulation of a test tube full of DNA well outside the realm of what is currently possible.
As a result, many people choose to work with models that approximate what happens quite well in practice, but break when pushed to extremes. One example of this is the abstract tiling model, which it turns out is NEXP-complete (see Gottesman and Irani's paper from FOCS last year).
-
$\begingroup$ Thank you for the intelligent idea, to view DNA computing as a physical system! I am going to look at the paper you have linked. Thanks again. $\endgroup$ Nov 4, 2010 at 11:25
-
$\begingroup$ @Aadita: No problem. Hope it is useful. $\endgroup$ Nov 4, 2010 at 11:27
-
1$\begingroup$ The Wang tiling model is not intended to model physical dynamics. When interpreted as a tool to predict the future state of a physical system, what a valid Wang tiling does is predict the most probable state of a system at thermodynamic equilibrium; i.e., lowest energy. But thermodynamics gives no clue as to how long a system might take to converge to equilibrium; for that you need kinetics. Many systems have a thermodynamic equilibrium that is achieved only after exponential time. For "physical computational complexity", use kinetics, not thermodynamics; e.g. the tile assembly model. $\endgroup$ Nov 10, 2010 at 18:51
-
$\begingroup$ @Dave: Thanks for the info. I must admit I am quite ignorant of the area, and perhaps have phrased that part of the answer very badly. I didn't intend to claim that it was believed to be a model the dynamics. $\endgroup$ Nov 11, 2010 at 3:06
$\begingroup$
$\endgroup$
This is a partial answer
From Wikipedia article you mentioned, Molecular DNA-computing algorithms that solve NP-complete problems do not prove that NP-complete problems are solvable in polynomial time on sequential machines (assuming feasibly in practice means polynomial time). DNA-computing can be considered a form parallel computing. Finally, from the viewpoint of computability theory, DNA-computing is no more powerful than Turing machines.
answered Nov 4, 2010 at 10:04
$\begingroup$
$\endgroup$
2
This paper might be interesting to you -- incidentally, I would be grateful if someone could clarify the shocking statement that constitutes its title.
answered Nov 4, 2010 at 9:39
-
2$\begingroup$ Some problems outside PTIME can be solved by parallel machines in polynomial time. This is not paradoxical, since PTIME talks about the problems solvable by a particular class of sequential machines in polynomial time. $\endgroup$ Nov 4, 2010 at 10:09
-
5$\begingroup$ I tried to clarify in the answer I have posted. $\endgroup$ Nov 4, 2010 at 10:53