4 ms·
From the conclusion of the paper: > In conclusion we have demonstrated experimentally a deterministic memcomputing machine that is able to solve an NP-complete
by bglazer 12y ago
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.
- Chinjut 12y agoThey 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).
- bglazer 12y agoOk 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?
- Sharlin 12y agoThere 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.
- JacobEdelman 12y agoWell, 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.
- bglazer 12y agoDid they actually build one? I got the impression that they have a working memcomputing machine, albeit one that is non-universal.
- JacobEdelman 12y agoDid 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.