Using DNA to Solve NP-Complete Problems (1995) [pdf] | Hacker News Reader

Using DNA to Solve NP-Complete Problems (1995) [pdf]

pdfs.semanticscholar.org

47 pointsaburan2831 comments

I co-wrote a thesis which touches this type of problems. The idea is that DNA is a very concentrated and massively parallel computing medium. However after all it's only kicking the can along the road. Citing myself:

«If we had a computer based on chemistry working a million times faster, then we could add twenty more variables to the SAT problem (the dual logarithm of a million is roughly 20). This is better, but not much better. If we want to add 100 more variables, we would run into problems. Suppose we need 2^100 water molecules with a molecular weight of around 18, then they would weigh 18·2^100/NA ≈ 38·10^6 grams or around 38 tons (NA being Avogadro’s number). With a few more variables we would need more water than there is available on the earth. This is the limitation of the memory for time tradeoff.»

PDF: https://goo.gl/J22sZP

Please do not use tiny URLs for links; your link redirects to:

http://saces.ly5.ch/saces.pdf

Sorry. I understand your concern. I used goo.gl for easy tracking clicks. Here the stats: https://goo.gl/#analytics/goo.gl/J22sZP/all_time

Excuse my naivety but I don't follow.

You need 2^100 water molecules to do what?

DNA has 4 bases, so any strand of 100 pairs can be encoded 4^100 ways. Granted DNA weighs a lot more than water.

I'm having a hard time understanding how a calculation can be encoded and performed. Can anyone provide an example of how this works?

This was only a thought experiment to show that even an absolute massive parallel approach with gazillions of computing entities doesn't really solve NP complete problems. Even if we could use a single water molecule as a simple computing entity, for problem sizes of about a few hundred variables or more we wouldn't have enough water in our whole world.

So it's ultimately hopeless without even going into detail how to use water as a computing medium.

However, for SAT there are practical solutions with heuristics back-tracking for many instances. So don't get worked up too much.

Under what plausible circumstances would you consider DNA-based or chemistry-based computation to be a superior solution compared to silicon-based computation?

Currently neither DNA nor chemistry is superior to silicon. Adleman made a proof of concept that DNA could be made to execute computations. So at least it's doable, but practically it doesn't make sense.

And nowadays ASiCs for accelerating deep learning is the best we have for massively parallel computation, I think.

It's more about thinking what we could do if we had gazillions of little things swimming in a solution or sitting on a die that could do computation for us. For me one important result is that it doesn't scale for huge NP complete problems. Add a few hundred more variables to a SAT problem and you don't have enough water in our whole world.

This reminds me of the old story of doubling the amount of rice for each square on a checker board.

https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem

The linked paper discusses using its enormously parallel nature to quickly solve large instances of NP-complete problems.

Aside from this, imagine taking a "smart" medication that uses biological computation to determine exactly where/when in your body to optimally release the medicine.

Your second sentence makes sense to me. That capability is a clear advantage.

I wrote an article that explains this result with pictures. You might find it helpful for understanding it: https://luckytoilet.wordpress.com/2016/07/28/a-brief-introdu...

The key insight from Adleman is that DNA complement binding allows for massively parallel "brute force" for the HPP. This exploits the fact that chemically, complement pairs will "find" each other given enough time, so if we encode all pairs into complements, then we know that every matching corresponds to a path.

An unanswered (although touched upon; unanswered I suspect because it is in the source paper) question in the paper is: why does this not mean P=NP if we only require O(m) test tubes and "mixing" operations on a formula of size m? The answer I suspect (I haven't read Adleman's paper) has to do with the amount of time it takes for the "mixing" operation to work. I would imagine that as the number of clauses increase, the number of DNA strands in the test tube increases, and the time it takes chemically finding your complement would increase exponentially. I'd be interested in the real answer though.

On a slightly pedantic note, even if the mixing operation were truly constant time, it would have no impact on P?=NP. There is no reason to believe that all computers that can be physically constructed are deterministic.

A physically-realizable system for solving problems that are NP in polynomial time, mass and energy would be very economically interesting, just as quantum computers are for Shor's algorithm and simulated annealing. (despite the fact that we can't yet perform Shor's algorithm at scale and at as far as I know some people still raise doubts about whether D-Wave's product truly outperforms computational simulated annealing or truly does anything "quantum")

It also gives us insights into one of the other interesting questions of our day: Is simulating a physical system of polynomial size in P, or not in P? If you find that polynomial-size physical systems can solve problems in NP but believe that P≠NP, then you would also believe simulation is not in P.

Absolutely. I didn't mean to imply it wouldn't be interesting. It just wouldn't have any impact on the question of P vs NP from a logocal perspective.

Also, with respect to your physical system argument, I'm not sure I agree. Any computer that actually exists has some probability of making a computation error. With that in mind, simulating a physical system with a step that involves becoming a physical system is likely not a valid argument from an algorothmic reduction point of view.

I remember the first time I saw a talk on this stuff. I was fully expecting to see pseudoscientific bullshit, and it was really surprising / exciting to see a serious, semi-practical scheme instead.

To followup, this is work by Dick Lipton, a very respected complexity theorist.

I thought it would be more of a joke article:

1) Start with DNA in a primordial soup

2) Wait ~4 billion years

3) An intelligent lifeform will create an A.I. that can solve it

I never thought it would work, but the last hundred years or so really sold it for me.

Tl;dr per my read

1) Convert the graph representation to a biological encoding that leverages DNA's complement binding.

2) Shake

3) Read unique newly bound sequences that contain your desired properties (e.g. start at X, end at Y), which will by chemical properties include all possible answers with high probability

The encoding seemed the tricky / novel part.

I don't understand this.

How is the DNA encoding the computation? I understand base complementing but how exactly does this result in an answer. If it were possible why didn't they do an experiment?

Read the paper of the inventor. It is easier. Adleman, L. M. (1994). "Molecular computation of solutions to combinatorial problems". Science. 266 (5187): 1021–1024. Bibcode:1994Sci...266.1021A. doi:10.1126/science.7973651. PMID 7973651.

There seems to be so much potential in alternative computing technologies. Why is nobody setting out to build one? (with the obvious exception of quantum computing)

Perhaps you could suggest some alternative technologies worth investigating? This DNA computation method is interesting but would only be useful for a narrow range of problems. There's DWave's quantum annealer which is showing a distinct lack of promise. Quantum computing will arrive eventually and is well studied.

Most alternative techniques I've seen try to use some analog technique to solve a difficult problem. The problem is that scaling the size of the problem requires ever less noise and more accuracy of these techniques and we quickly hit a wall in every case. Memcomputing, for example, can't practically encode more integers than we can test using silicon processors. There's no version of the fault tolerant threshold theorem for analog computers to fix this deficiency.

So really, of all the alternative technologies I've read about, it's only DNA based methods that I'd really be interested in seeing more of.

(1995)

Thanks, updated!

Pretty sure this is 'fake' and a old article.

Why is DNA better than silicon? Is it magic?

Have you read the article, or are you just responding to the headline/title?

EDIT: Seeing as I got a downvote I thought I'd expand on my question. You asked:

  > Why is DNA better than silicon?
  > Is it magic?

The article says clearly what the advantage is of DNA over silicon - it's at the very top of the second page where it says:

  > ... biological computations could potentially
  > have vastly more parallelism than conventional
  > ones.

Secondly, the article isn't "fake" in any sense of the term - it's written and published by an eminent researcher in the field of computational complexity. It's a very clear exposition of the techniques used to solve NP problems with physical systems, including an analysis of why this doesn't really work, and why it's unlikely ever to work.

Yes, it's "old", although for some of us it's not that old, and given comparatively recent excitement about using slime-molds to plan "optimal" transportation networks, clearly it's still relevant, and not well enough known.

So my question still stands - you seem to have dismissed this quickly, and I wonder if you've actually read and understood it, or are you simply reacting to the headline/title?

> ... biological computations could potentially > have vastly more parallelism than conventional > ones.

I think it's all the same. There is no magic to biological?

> you seem to have dismissed this quickly, and I wonder if you've actually read and understood it

I think I did read it first time quite well, my problem is it's tiring to re-talk about old articles , but to be honest rereading things that logically don't make sense I don't do, so maybe I'm lazy.

There is no magic, and the article makes that clear. It might win on the constant because of the potential parallelism, but even that's not clear. But if it did win on the constant, the amount of potential parallelism is huge! It's just that we never seem to be able to take advantage of it "properly."

But the thing is that this idea keeps getting re-discovered, with people getting excited all over again. This article is a clear debunking of the hype, and has value in being able to point people at it and say "Look, it's been done, it doesn't work, and here's the explanation. If you've done something really new, then you need to make it clear why it's different from this 20 year old work."

Having said all that, I'm not sure what it is you're claiming doesn't make logical sense.

Lipton is legit. In page 1 though

> However, it does _not_ mean that all instances of NP problems can be solved in a _feasible_ sense.

Basically, this says nothing about the P vs. NP problem (as I'm sure many are thinking of when NP is mentioned). This is more about a non-trivial utilization of the massively parallel properties of DNA computers in order to speed up brute force computation.

Reply on news.ycombinator.com