Hacker News Reader

Comment by bglazer | Hacker News Reader

From the conclusion of the paper:

> In conclusion we have demonstrated experimentally a deterministic memcomputing machine that is able to solve an NP-complete problem in polynomial time (actually in one step) using only polynomial resources. From complexity theory we then know that we are able to solve any other NP-complete problem in polynomial time. We stress again that this result does not prove NP=P, which should be proved only within the Turing paradigm.

I'm very confused by this statement. If their Universal Memcomputing Machine is able to solve any NP problem in polynomial time, what is the relevance of whether NP=P in a Turing machine context?

Also, this seems like a very important result, but my skepticism is really high.

View on HN

They are guarding themselves against charges that they have claimed something which they haven't (to have proven that NP = P in the standard Turing machine context, and thus earnt the accolades which would accompany the resolution of this longstanding mathematical problem).

Ok that makes sense. From a practical perspective, would this essentially make Turing machines obsolete in solving NP problems?

Essentially does this mean that NP=P, in a non-Turing machine context?

There are plenty of formalisms that can solve all of NP in polynomial time. Problem is, they are all theoretical and there is no compelling reason to believe any of them can be actually constructed given the laws of physics.

Well, we don't know if we can build UMM's. This does seem to strongly contradict a lot of ideas that no computational system in the physical world will be able to beat a Turing Machine exponentially. In a way UMM's right now are just saying "what if we can do this special computing thing" and proving that than P=NP. It only becomes surprising if we can actually build them.

Did they actually build one?

I got the impression that they have a working memcomputing machine, albeit one that is non-universal.

Did they build something that can break P=NP? No. If I'm right then I'll look smart and if I'm wrong than I'll be too excited to care. Also, if I'm wrong I have to go to a quite retreat somewhere and rethink the nature of reality.

Reply on news.ycombinator.com