Comment by yifanlu | Hacker News Reader

Comment by yifanlu | Hacker News Reader

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.

Reply on news.ycombinator.com