DNA Solves Million-Answer NP-Complete Problem 169
cybrpnk writes: "A 'DNA computer' has been used for the first time to find the only correct answer from over a million possible solutions to a computational problem. Leonard Adleman of the University of Southern California in the US and colleagues used different strands of DNA to represent the 20 variables in their problem, which could be the most complex task ever solved without a conventional computer. Details to be published in Science."
Nice, but... (Score:1, Informative)
Still, impressive!
Real article (Score:5, Informative)
Re:Which problem? (Score:2, Informative)
Re:Which problem? (Score:2, Informative)
If memory serves me correctly, the problem described in the REAL article [usc.edu] is a 3-SAT, but algorithmics class was years back and beginning to fade from memory...
What is P vs. NP and why should I care? (Score:5, Informative)
Or check out The P versus NP Problem [claymath.org] at Clay [claymath.org] for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? [vb-helper.com] at VB Helper for a little more info.
Ok, but what is it good for? The Compendium of NP Optimization Problems [nada.kth.se] is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling [nada.kth.se] to multiprocessor scheduling [nada.kth.se].
Hopefully that helps. I was very clueless when it came to P vs. NP stuff that always seems to be mentioned on Slashdot. So I took the time to look it up. Now I'm clueless but I have links to share. :)
Errata: First Complex Electronic Solutions (Score:3, Informative)
Although the author may be responding to Seymour Cray's first supercomputers circa 1960 [digitalcentury.com] it is untrue that complex computations weren't being performed electronically until the 1960s.
The History of Unisys [unisys.com] shows the earliest milestones with the following one almost certainly qualifying as "complex computation":
1952 UNIVAC makes history by predicting the election of Dwight D. Eisenhower as U.S. president before polls close.
Comparable to 1960s computers (Score:3, Informative)
The description of the problem they are solving corresponds to a 3-SAT (propositional satisfiability with clauses of length 3) instance. In 1962 Davis, Logemann and Loveland published a paper entitled "A Machine Program for Theorem-Proving", in which they described a computer program which could solve SAT problems of a similar size, extending earlier work by Davis and others published in 1960. (You can read the paper in Communications of the ACM if you have a library that goes back that far.) So it looks like their comparison is correct.
The method they are using for the DNA computer is rather crude compared to that proposed by Davis et al, whose procedure is still in use today for solving SAT problems. We can now solve problems with thousands of variables, and actually do useful things in the process (e.g. verify hardware specifications).
The A in RSA (Score:1, Informative)
Ironic, by showing how to do 0computation with DNA he may be undemining RSA!
Re:Which problem? (Score:3, Informative)
Re:Nice, but... (Score:2, Informative)
Re:Real article (Score:5, Informative)
Re:don't hold your breath (Score:3, Informative)
Not quite. If you have a class of problems, characterized by some parameter n, then for large enough n, the problems in a class that is NP will get harder with increasing n faster than they would if the class was P.
But for any particular instance of a class of problems, it doesn't really matter what the class is--in fact, you can construct example problems that would be NP if generalized in one way, P if generalized another, or even constant time if you choose a perverse "generalization" (e.g., n=date on which the question is posed).
Saying that the problem was NPC is a red herring; what they are actually doing is making a time/space tradeoff which would be hard of conventional computers, and then solving a particular example problem (not the class of problems).
-- MarkusQ
Re:don't hold your breath (Score:3, Informative)
The reason I replied to your original comment was that you implied that the work wasn't useful, or wasn't as much of a breakthrough as Adleman claims. Saying that they only solved a single instance isn't relevant: they have a method that works on any 3-SAT problem for which they can construct a long enough DNA chain to represent an assignment, and they have an implementation that actually finds the solution.
Don't forget that the first practical computer algorithm for SAT (Davis and Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM, 1960) didn't even have a computer implementation: they demonstrated its usefulness by working an example out by hand!
Re:Which problem? (Score:1, Informative)
Well tell them than a 24-clause 20-variable 3-SAT problem isn't very hard. You can number the variables in an arbitrary way, sort the clauses by "smallest index variable it uses" and start assigning values from the end. You only need very little guesswork.(Yeah, I'm contesting the claim that "A DNA-based computer has solved a logic problem that no person could complete by hand")
You need about 5.1909 times more clauses than there are variables to get a "tough" 3-SAT instance. That means 104 clauses, not 24.
Recent 3-SAT results for "normal" computers (Score:2, Informative)
Note, these problems are 5 times larger than the one solved by the DNA computer and likely much harder (the DNA one sounds very underconstrained).
Both complete and incomplete solvers are shown:
Note: Things don't really get interesting until you get up over 500 variables for hard, random 3-SAT.
The 'A' in RSA (Score:1, Informative)
Article on "How a DNA Computer Works" (Score:2, Informative)
(This is a good starting place if you want to know the basics.)