Slashdot Mirror
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."
Where is the promised press release here?
Video Game cheats, hints a
now, one needs to ask - "can this same technology be used to break codes/algorithms used within security?" the article is a bit lacking in details of how they achieved this exactly, but, koas theory is in action here.
But with only a million different combinations - surely this is no match for today's computers yet! How long will it be before it can be used for more practical problems?
Video Game cheats, hints a
The article is a bit garbled (exponential time != NP-complete!) so it's a bit hard to work out what problem they were looking at.
I'm guessing 2-SAT; can anyone confirm/deny this?
Tarsnap: Online backups for the truly paranoid
this doesn't make NP-complete problems polynomial ofcourse.
Still, impressive!
Our old binary digit computers have been around for AGES (50+ years in tech time ;-)
It is really the time for searching new and more complex computer architechtures if we ever want to have true IA (a la HAL 9000). I always wondered why ppl insist on building neural nets based on ordinary computers rather than building them on dedicated neural hardware (expeeeensive, but needs to be tried more often).
Of course, today's computers do a good job resolving them, but there are too many architechtural limitations. Brains are a hella lot older than computers, and a hella lot more advanced (but very fragile).
Way to go dudes.
``If a program can't rewrite its own code, what good is it?'' - Mel
Here is the article at USC which covers the subject, including an interesting picture!
...it's not a bug it's a mutation.
Which OS did they use? Microsoft DNA?
*rimshot*
"Black holes are where God divided by zero." - Steve Wright
I must resist my urge for an inane beowulf cluster comment here....so instead...can you imagine a beowulf cloned with one of these?
If Mr. Edison had thought smarter he wouldn't sweat as much. --Nikola Tesla
at least we would have a benchmark of sorts.
I imagine that the problems of creating a truly AI computer will be solved using a DNA based computer.
;-)
"It is a greater offense to steal men's labor, than their clothes"
Adleman and co-workers expressed their problem as a string of 24 'clauses', each of which specified a certain combination of 'true' and 'false' for three of the 20 variables.
looks like 3SAT to me.
So they had to go through and find all the possible answers and put them in the mix? I don't think this will every be a viable solution when to find the correct answer you have to know all the wrong ones as well. Part of problem solving is starting out with 0 answers. I bet they couldn't use the DNA computer to figure out all those 1048576 wrong solutions. Although I think it would be an interesting concept, until they can figure out a way to solve problems without knowing all the answers, I do not see how it could be used for serious calculations. I think it could possibly be the next great search engine, or maybe an RC5 engine. But how long would it take to encode 18,446,744,073,709,551,616 strands of DNA?
The REAL article states that
... device ..., electrons will be our computing friends for the foreseeable future.
"It would take a breakthrough in the technology of working with large biomolecules like DNA for molecular computers to beat their electronic counterparts".
So while the article also mentions code-breaking as an obvious application for this
Black holes are where God divided by zero
And to think, LSD made this all possible
"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.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
Two years ago I bought
ISBN 3-540-64196-3
which discussed Adlemans experiements.
How could this article describe it as the "first" dna computer used to solve a problem?
Someday, I'll have a real sig.
It looks like you're attempting mitosis. Now would be a great time to sign up for a Passport account. WARNING: Are you sure you want to attempt mitosis without a Passport account? Your ancestors may regret it!
And on the other side of the coin, the Open Source DNA advocates will be saying:
You don't need a Passport account to have kids, honey. Yes, it's perfectly safe. Support? Who the hell told you Microsoft was going to support our child?! A free PC?!
According to Adleman and co-workers, their demonstration represents a watershed in DNA computation comparable with the first time that electronic computers solved a complex problem in the 1960s. They are optimistic that such 'molecular computing' could ultimately allow scientists to control biological and chemical systems in the way that electronic computers control mechanical and electrical systems now.
Huh? What they did here is use the self-construction property of DNA whereby only the respective nucleotides A, T, C, and G only form a bond with their compliment.
That means you can have millions of solutions and the whole thing will solve itself because only the correct solutions 'fit' into the problem which you have represented in the ATCG language. You can do the same thing when you add more variables, and it's just as easy. That is something very hard to do with electronic computers, because they deal with information on the quantity level whereas DNA is able to solve a problem on the problem "abstraction" level itself.
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. A DNA strand is infismal compared to today's current Si processes, where we measure things in micrometers. DNA is in the single nanometer range. That's several 100 times smaller than a single wavelength of light.
I don't think DNA will be viable for most standard computational tasks, or for a practial turing machine. Biological systems don't use DNA to do logical operations (that I know of), and the only thing they use it for is for data storage (instructions for building proteins). The only operations (under normal circumstances) an organism does with DNA is copy. Mutations (reversals, transpositions, etc.) occur because of chemical errors. That is the only operation it does really.
This all seems very interesting albeit limited to the lab.
"I'll just chip in a bit for RedHat: I actually have that installed on my university machine." - Linus, '95
Or check out The P versus NP Problem at Clay for a really good description (unfortunately too long to quote here). And lastly, you might want to check out Tutorial: Does P = NP? at VB Helper for a little more info.
Ok, but what is it good for? The Compendium of NP Optimization Problems is a great place to look for real world examples of NP problems. Including everything from flower shop scheduling to multiprocessor scheduling.
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. :)
-- null
It's amazing the things possible with DNA computers, little tiny ones implanted in the human brain.
Of course, it won't be long until people are over clocking. Or worse, adding transparent case mods. *shudders*
You took it very seriously because it hit a hot button.
There is a technical term for the comment I made about a DNA based AI computer.
It is called a "joke".
This is because of the cognitive dissonance between the usual attempts at AI using wires and cirsuits and such, the DNA from living creatures, where some form of awareness and intelligence can occasionally be found.
go have yer morning cup of coffee, and relax. perhaps you didn't see the smiley face in the original post.
"It is a greater offense to steal men's labor, than their clothes"
Clearly the problem was 3-SAT.
Although the author may be responding to Seymour Cray's first supercomputers circa 1960 it is untrue that complex computations weren't being performed electronically until the 1960s.
The History of Unisys 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.
Seastead this.
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).
I already knew something about P vs NP but some of these links have really non-technical easy explanations.
I am particularly enjoying the one on the link between Microsoft Minesweeper and NP complete problems
(Yes I remember when it was reported here, but it only linked to the guys academic paper which was too deep for me)
The only reason all cover-ups appear to fail is that you never hear about the ones that succeed.
Well, the way you stated the problem, all problems are solvable (on a digital computer) in linear time wrt problem representation The most amazing order I've seen so far.
Hint: char alphabet[]="AGCT";
Gentlemen, you can't fight in here, this is the War Room!
Well, any computer can be used to attack crypto algorithms, it's just a matter of whether the computer can do so in a reasonable amount of time (like, say, the lifetime of the universe :) ). With current technology, it is not possible to break these algorithms, because the problems they are based on are believed to be hard. You can view this DNA computer as simply just being a new architecture, like Intel or SPARC. It's cool, but it has no effect on the dificulty of problems. The computing models computational complexity theory is based on are mathematical, and do not depend on any physical implementation of a machine.
Quantum computers are a slightly different story. They are theoretically non-deterministic machines that can solve all problems in NP in polynomial time. In theory, with a big enough quantum computer you could break all currently used encryption schemes, but in practice, no one has really come close to building a quantum computer to actually do anything non-trivial let alone useful. I've heard it suggested (I don't really know anything about quantum mechanics, so maybe the physics geeks in the crowd could comment on this and let me know if I'm full of crap) that it may be the case that while a quantum computer may be able to solve NP-hard problems in polytime, the difficulty and complexity of building such a machine might be proportional to the difficulty of solving the problem in P.
If this is the case, then even if it's theoretically possible to build quantum machines to break known crypto algorithms, in practice it would be infeasible to do so. If the complexity of building the machine doubles when you add a qbit then you may as well just use a deterministic computer and wait a few billion years for your answer.
This is Leonard Adleman .. the A in RSA, difficult to tell from his homepage .. unless u dig. i guess he keeps in low key.
Ironic, by showing how to do 0computation with DNA he may be undemining RSA!
Imagine a Beowulf cluster of these!
:)
But seriously, I imagine these things must be pretty slow, since they are powered by chemical reactions. I don't forsee one of these babies supplanting my desktop any time soon. Of course, the whole point is that this shows the power of genetics, and it is amazing in that sense, to think that life is basically created by computer programs. Fortunately Microsoft hasn't gotten into the DNA software market yet, I'd hate to have bugs growing out of my skin and stuff.
if a byproduct of that solutions of problems
becomes a monster (some cells actually incorporated problem DNA-s).
WoW!
It seems to me that the amount of preparation that went into constructing the long strands and each of the truth sets is extensive. For this type of computing to become useful, it would appear to me that this construction of the parts necessary to carry out the computation would need significant work. I am very, very hopeful that DNA based computing as well as quantum molecular based computing will begin to make rapid gains in the very near future. The potential to astronomically increase the available computing power is there, I've read all the theories. It just needs to be made to happen :)
... quantum computing devices become common, as do DNA based computing devices - each in their own niche, possibly (neither device may be promising as a 'general computing' device, but used in conjunction they may complement each other) and the article previously posted about table-top fusion from the collapse of bubbles provides us with practically limitless and clean energy to drive the energy needs of all our computing devices. I can't wait :)
:)
Just imagine
Add to that the possibilities for human augmentation by cybernetic implants and I feel that the day of Gibson's Neuromancer may be soon approaching. As the geek I am, I can't wait
This is interesting, but would it have worked at all if the scientists did not know the answer already? I mean, they set up all the variables, and then they set up all the possible answers, and the DNA just matched up with the one that they already knew to be correct. What if they didn't know which one was correct? What if there were a billion possible answers? Would they have to program them all in? At what point is it actually faster to use a computationally inefficient conventional PC instead because the compiler does the brunt work for you? Is this DNA method ever faster?
Obviously, there are a lot of questions to be asked about this, but it will be very interesting to see what happens when somebody develops some kind of compiler for the DNA computer, and you can just input an equation and some parameters and in several minutes you have the answer... But until then, this doesn't seem all that useful. On the other hand, it is fascinating research, and by all means, they should continue research on it.
Lack of eloquence does not denote lack of intelligence, though they often coincide.
As a testimate to the parallel computing power of DNA computers, an entire planet of DNA computers has produced the answer to the universe. However, now we must wonder as to what question this answer applies....
meh.
The details are a repost, this technology is "old" as in they did this same problem with travelling salesmen 2 years ago. Details were posted in SCIAM.com
internet like monkeys'
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.
...that DNA computation offers no theoretical advantage over Turing machines. That is, problems that are thought to take an exponentially increasing number of steps on a regular computer still do with the DNA computation model. The DNA method requires that every combination be exhaustively generated, and therefore the number of molecules required grows exponentially with the input size. Of course, the DNA method offers some practical advantages over today's computers (when it comes to this type of combinatorial problem.) The computational elements (DNA molecules) are very small and can "swim around" in three dimensions to make many more combinatorial "decisions" than could be hardwired onto a piece of silicon today.
Chaos is a name for any order that produces confusion in our minds. --George Santayana
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.
sig intentionally left blank
I remember reading an article in Dr. Dobbs journal from something like 1993 about how Adleman used DNA computation to solve an instance of the travelling salesman problem. How is this work really revolutionary then, aside from demonstrating the use of molecular computation techniques on a more complex problem. As far as I can tell this isn't 'news' so much as it has already been done, published and publicised before, by the same physicist/mathematician/biochemist.
-K
The problems that can be solved in a practical manner with dna computing are small. For real problems, you need a sea full of dna. Bummer.
no sig error.
I remember reading an article about this in a class I took arround this time last year. And it wasn't even a new article... Very interesting tho, nice implementation of parallel computing :)
"Question with boldness even the existence of a god." - Thomas Jefferson
> You can view this DNA computer as simply just
> being a new architecture, like Intel or SPARC
nope, Intel and SPARC are serial architectures. This DNA computing is fundementally different. It's actually trying solutions in parallel. Since all the DNA chains are trying to link together at once, you can view this as simultaneous computations to the order of some number relative to the ammount of DNA you've got in your tube. In this way, you can view the DNA computations as more relative to quantum computing. The only problem is, there's a lot of time and money involved in setting up the ccomputation, and in finding your solutions from the muck. Whoever figures out a way to use DNA to crack encryption codes will probably really really really want to figure out what's in those files!
I read an article on this last year for a class I was taking, so it's not really new, as this article states. You should take a look arround the web for a good article and give it a read, it's very interesting.
"Question with boldness even the existence of a god." - Thomas Jefferson
let me shed a little info on this work for you guys. i'm a graduate student working in len adleman's lab--i'm not an author, but i am very familiar with the details of the project. first off, concerning the complexity of the problem: we like to say that this is the first truly non-trivial problem solved with a DNA computer. len's original traveling salesman problem (solved in 1994 and published in Science) has something like 4 cities and could be easily solved by a human with pen and paper in a matter of seconds. subsequently, several other NP-complete problems have been attempted: most notably the "knight problem" (how many and where can one place knights on a chessboard so they cannot attack each other) and 3-CNF-SAT (3-conjuctive normal form satisfiability) with no known polynomial time algorithm (not including quantum polynomial tome algorithms). this work is a 20 variable instance of 3-CNF-SAT, with a combinatorial diversity of 2^20 possible outcomes, meaning ~ 1 million possible solutions. the 3-CNF-SAT problem was contrived to produce only 1 possible combination that would satisfy the formula. for a human with pen and paper, this problem would take several hours, if not days, using a brute force method of attack. an electronic computer, however, would solve it in a matter of seconds. so to draw an analogy, the DNA computer is probably somewhere near the ENIAC was in the 1940s. Electronic computer development was growing rather slowly until the development of the transistor in the 1950s, and we have been benefitting from Moore's Law ever since. a similar technological breakthrough will be needed for DNA computers to seriously rival the computational power of silicon.
I don't think DNA will be viable for most standard computational tasks, or for a practial turing machine. Biological systems don't use DNA to do logical operations (that I know of), and the only thing they use it for is for data storage (instructions for building proteins). The only operations (under normal circumstances) an organism does with DNA is copy. Mutations (reversals, transpositions, etc.) occur because of chemical errors. That is the only operation it does really.
this is not entirely true. nucleic acids are responsible for quite a few things in the cell. yes, DNA is not very reactive, designed to be a stable archival form of genetic material, but RNA (ribonucleic acid) is a different story. derived from DNA, it has a 2' hydroxyl (-OH) group on its sugar (hence the name ribo- instead of deoxyribo- which has a 2' hydryl (-H) group) and is much more reactive, causing cleavage, ligation, and other enzymatic modifications. there are programmed errors and very regular processes in the cells, things like SOS DNA repair, nonhomologous end-joining, and crossing over, that can result in modification. there is so much here to study it can make your head spin! so don't count any of it out =)
As a grad student at MIT, Leonard Adleman helped invent the public key crypto algorithm know as 'RSA'. The other two gents were Ron Rivest and Adi Shamir (the 'R' and the 'S').
There is one serious flaw in DNA computing that people are sweeping under the rug, and that's that although the amount of time needed to solve the problem does not increase exponentially, the amount of DNA does. Off the top of my head, I don't know the amount of DNA needed to perform a given calculation, but one of my professors who works on this sort of thing showed us once that a calculation that could be done in a reasonable amount of time on a standard desktop computer would require more DNA than there is on earth. I'm sure there are ways to increase the efficiency of the process, but this is still a fundamental limitation of this type of computing.
What would happen if NP-Complete was solved?
Many responses (IIRC) were regarding encryption encoding...
several days after that article I ran across something that
suggested the potential benefits far outweighted not doing it.
Something regarding Space as in outer space and it's safety of us in it.
Anyone have links to such information, as I seem to have forgotten and lost out of browser cache the link.
How is solving the NP-Complete problem useful to NASA?
In other words, this technology is faster than anything that can be or is likely to bedone on silicon.
;).
...For problems that are easily parallelized to order 1e24 nodes
On the other hand, rendering Quake is massively parallelizable...
Now we just need to show that N = 1... :-)
Printable version of the article found here.
(This is a good starting place if you want to know the basics.)
You are missing my point.
My point is that if your algorithm is exponential time, I can ALWAYS beat your machine. All I need to do is double the size of the input I give you, and you're forced to SQUARE the speed of your machine to keep up. The only way you can build a machine that can defeat me is if it is a non-deterministic machine (which DNA computers are NOT), or if P=NP and you manage to find a polytime algorithm, which is unlikely.
Consider your example of a 610g DNA computer. And forget about the setup time and let's assume you can perform 10^23, or let's say 2^80 computations per second, and that you never have to intervene to re-configure the machine after exhausting the solutions you're trying. It would still take you 2^944 seconds to solve a 1024-variable instance of 3-SAT. Even if you build one of these that uses 610kg of DNA, the factor of 2^10 speedup would be insignificant. Now you can solve the problem in 2^934 seconds -- big deal! In fact, you could NEVER solve a 1024 variable instance of 3-SAT by naively testing all possibilities using a DNA computer because there aren't enough particles in the universe to represent even a tiny fraction of the solutions!
Maybe you know all of this already. But the poster I was responding to suggested (at least in my interpretation of his post) that these DNA computers are comparable to quantum computers, and that "maybe" eventually they could be used to solve hard problems such as those which are used in cryptography. And that's still absolutely false, unless P=NP, since there are crypto algorithms based on NP-complete problems. Even those which aren't (factoring) are believed to be hard enough that they probably aren't vulnerable (only current key sizes would be).
You are missing my point.
:) :) :)
I'm not missing your point. I understand the difference between having massively parallel system and something that is not deterministic
In fact, you could NEVER solve a 1024 variable instance of 3-SAT by naively testing all possibilities using a DNA computer because there aren't enough particles in the universe to represent even a tiny fraction of the solutions!
Thats a strong statement. It assumes that all solutions have to be present at once, not sequentially over time, or indeed that a DNA computer has to have all the solutions prefabricated in the first place. It is possible that DNA computers could assemble the answers from base pairs, for example.
My point is that if your algorithm is exponential time, I can ALWAYS beat your machine.
As I understand it, quantum computing currently has extreme scalability problems going beyond a few (? 11 AFAIK) qbits, as its hard to make a molecule big enough to hold all the quantum states.
So you make that comparison based on my worst case scenario (that every answer has to be prefabricated), your best case scenario (that you can read the quantum state of a large molecule), and the assumption that you can simply increase the complexity of a problem until a non deterministic approach is faster.
Personally, I was just commenting that DNA compting is very, very fast in principle. Perhaps we ought to rething 128 bit key lengths even on the basis of this. By the way, if quantum computing becomes practical, just how long will the key length need to get
My 2c worth
Michael
There is no cryptographic solution to the problem where the intended receiver and the attacker are the same entity.