patternMinor
Universal memcomputing machines (UMM)
Viewed 0 times
universalmemcomputingummmachines
Problem
This paper on memcomputing seems like a really big deal, but it doesn't seem to be particularly popular. They prove that their UMM can solve NP problems in P, although they don't claim P = NP. In their next paper, they go on to build a physical model of this UMM with moderate success. Does this mean P=NP?
Solution
The authors suggest a new computation model that solves NP problems in polynomial time. Another such model has been known for a long time – non-deterministic Turing machines. They can also solve NP problems in polynomial time. In fact, one common definition of NP is the set of problems solvable by non-deterministic Turing machines in polynomial time.
If the authors succeed in realizing their machine physically (which is doubtful), then this shows that the "efficient Church–Turing thesis", which states that all physically realizable computation models can be simulated by a Turing machine using only polynomial overhead – is false. Another candidate for refuting this thesis is quantum computers, but they are conjectured not to be able to solve all NP problems in polynomial time.
If the authors succeed in realizing their machine physically (which is doubtful), then this shows that the "efficient Church–Turing thesis", which states that all physically realizable computation models can be simulated by a Turing machine using only polynomial overhead – is false. Another candidate for refuting this thesis is quantum computers, but they are conjectured not to be able to solve all NP problems in polynomial time.
Context
StackExchange Computer Science Q#54164, answer score: 5
Revisions (0)
No revisions yet.