Slashdot Mirror

← Back to Stories (view on slashdot.org)

DNA Solves Million-Answer NP-Complete Problem

Posted by timothy on from the combinations dept.

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

4 of 169 comments (clear)

  1. Real article by mnordstr · · Score: 5, Informative

    Here is the article at USC which covers the subject, including an interesting picture!

    1. Re:Real article by bcrowell · · Score: 5, Informative

      And here's the group's web page, including their preprints and FAQ. No preprint of the present paper, though.

      --
      Find free books.
  2. And in 5 years Microsoft will say... by Ozan · · Score: 5, Funny

    ...it's not a bug it's a mutation.

  3. What is P vs. NP and why should I care? by rtos · · Score: 5, Informative
    Perhaps you are wondering what an NP-complete problem is or what this P vs. NP stuff is all about. You might want to check out the comp.theory FAQ and scroll down to 7. P vs NP. It gives a bit of history and a decent description.

    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