DNA Solves Million-Answer NP-Complete Problem

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."

LSD

[GigsVT]

And to think, LSD made this all possible [thegooddrugsguide.com]

"Would I have invented PCR if I hadn't taken LSD? I seriously doubt it,"

-- Dr Kary Mullis, Nobel Prize Winning inventor of the Polymerase Chain Reaction that allows pretty much all the modern research in DNA technology.

And to think on the same Google search that I found that, there was a sponsered link to "How drugs support terrorism" from the government.

Re:don't hold your breath

[isenguard]

However, conventional *serial* problems are something very hard to do with DNA, because it involves the manipulation of a single strand whereas you would be working in parallel with millions, even billions of strands for NP complete problems.

You are missing the point: NP complete problems (like 3-SAT, which is what they are solving with this DNA computer) are incredibly difficult for serial computers to solve. Nobody seems to be suggesting that DNA computers should be used for serial problems that we can already solve with conventional computers. However, being able to solve SAT (and hence other NP-hard) problems more efficiently is incredibly useful, because SAT problems exist that we can't (and might never be able to) solve using existing techniques.

Re:Is this new?

[Lictor]

Well it certianly isn't the "first" DNA computer to solve a problem. However, it *is* the first one to solve a problem that would be seriously non-trivial for a human to do by hand.

it's already in "Applied Cryptography" (B.Schneier

[rkit]

This is not exactly news. The second edition of "Applied Cryptography" by Bruce Schneier already mentions DNA Computing in the discussion of key size.

According to Schneier, Adleman was able to solve a Directed Hamiltonian Path Problem with 7 vertices already in 1994. It is interesting that it took 8 years to get from 8 to 20 vertices. The difficulties seem to be enourmous.

Allthough this seems to be excellent research, I still doubt that this is significant for solving real world problems. After all, this is a brute force search (although a massively parallel one). But there are physical limits to consider: there are ~10^50 atoms on this planet, but this only in the order of 42!. (read faculty of 42...) So 42 may not be the answer after all, but the size of the problem...

Modern algorithms for discrete optimisation can do much better than this. Travelling Salesman Problems in the order of several thousand cities have already been solved.

Re:don't hold your breath

[sh_mmer]

to the extent that the space complexity of DNA computers can be improved by clever encodings, the time complexity of classical computers can be improved using the same encodings.

that's simply because DNA computers are just a bunch of little computers which can be simulated with equal overall complexity (space complexity X time complexity) by one big computer. i'm not saying that DNA computers (or some other form of super-parallel computers) won't ultimately be much faster than conventional computers (i work with parallel algorithms in my research). what i'm saying is that exponential complexity algorithms won't be implemented in polynomial space and time, even by DNA computers, which is what the previous poster was implying (SAT is NP hard.)

cheers,