9
$\begingroup$

I came across an article published in Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states", which makes some pretty astonishing claims.

Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines. Therefore, they can solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size.

(Italics mine).

I would dismiss this off the bat as non-serious, given the strong nature of the claims, if it weren't for the fact that this was published in Science, and that related material by some of the authors was published in Nature Physics, in an IEEE journal and in Physics Review E, all of which are reputable peer-reviewed publications that wouldn't let such claims get published without them being serious.

So is it true? Can these people solve NP-complete problems in P-time using their model?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The answer to the last question is of course no. The definition of P didn't change just because someone invented a fancy new computation model. $\endgroup$ – Emil Jeřábek Jan 23 '17 at 19:09
  • $\begingroup$ @EmilJeřábek they didn't just invent a new computation model, they also claimed that it is equivalent to NP. $\endgroup$ – Alexander S King Jan 23 '17 at 19:21
  • 3
    $\begingroup$ You are getting something mixed up. If they had proved their model is equivalent to P, then this would imply that P = NP. $\endgroup$ – Sasho Nikolov Jan 23 '17 at 19:24
  • $\begingroup$ The abstract of the paper contains the statement: "It was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines." This just means that the two models are able to solve the same algorithmic problems. It des not mean, that polynomial time complexities translate again into polynomial time complexities. $\endgroup$ – Gamow Jan 23 '17 at 20:12
  • 12
    $\begingroup$ See chat.stackexchange.com/transcript/9446/2015/12/21, especially scottaaronson.com/blog/?p=2212 $\endgroup$ – Thomas Klimpel Jan 23 '17 at 22:58
11
$\begingroup$

I feel this has been answered sufficiently in the comments, so to just sum everything up:

  • The authors do not claim P=NP, which is a statement about deterministic and nondeterministic Turing machines.

  • The authors propose a model of computation that they claim to show is equivalent in power to nondeterministic Turing machines.

  • The authors construct physical machines that implement this model of computation for small input sizes.

  • The authors argue that building larger versions is physically realizable/possible with polynomial-sized resources.

  • This last claim, which is of course not proven and not really a formal statement, would imply a that it is generally physically possible to solve NP-complete problems with polynomial-sized resources.

  • Scott Aaronson in a blog post explains why this last claim is problematic and why the scalability of their approach has problems: http://www.scottaaronson.com/blog/?p=2212

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I'd like to note that as of today (Oct 2019), not a single researcher reproduced the NP-complete solver from this 2015 article. Moreover, in all related subsequent memcomputing articles by the same authors, there was not a single line of code that will assist in reproducing the NP-complete solver. $\endgroup$ – G. Cohen Oct 4 '19 at 16:48
1
$\begingroup$

The title of the memcomputing article is clearly problematic from a complexity theorist's viewpoint. There is no rigorous proof that the analog implementation of memcomputing would converge in polynomial time to the inapproximability gap for general optimization problems. Even if it does, that doesn't say anything about the $P=NP$ problem because you have to simulate the continuous system on a Turing machine. When simulating the ODEs that memcomputing operates under, you obviously have to be careful with discretization errors and the likes. There are some works on the robustness of these ODEs, but they are not fully rigorous. That being said, for all practical problem classes (and sizes), memcomputing (or rather the numerical simulation of it) does appear to outperform many state-of-the-art algorithms, but this is again purely empirical.

As for Scott Aaronson's criticism, it no longer applies to the newer memcomputing schemes, (see https://arxiv.org/abs/1810.03712, https://arxiv.org/abs/2011.06551, and https://arxiv.org/abs/2102.04557), which is much different than its original conception. The newer works also come with source codes for numerical simulation, see https://github.com/PeaBrane/Ising-Simulation

Improve this answer
New contributor
PeaBrane is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • $\begingroup$ @PeterShor fixed $\endgroup$ – PeaBrane 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.