10
$\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?

$\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$ Jan 23, 2017 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$ Jan 23, 2017 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$ Jan 23, 2017 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, 2017 at 20:12
  • 12
    $\begingroup$ See chat.stackexchange.com/transcript/9446/2015/12/21, especially scottaaronson.com/blog/?p=2212 $\endgroup$ Jan 23, 2017 at 22:58

3 Answers 3

13
$\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

$\endgroup$
2
  • 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, 2019 at 16:48
  • $\begingroup$ We made our implementation of the paper public on Github: github.com/daniel009988/dmm $\endgroup$
    – DanielM
    Jul 7 at 8:41
6
$\begingroup$

I would like to add some additional information to Daniel Primosch's answer from above. The figure with the results from the paper he cited is accurate. We got in touch with the authors a while back and did our own reference implementation of the digital memcomputing machine (aka "circuit") in C++, using the boost library for the ODE integration. We made this implementation public on Github for the research community. The authors used Barthel instances with increasing number of variables and clause:variable ratios. It is important to mention that all these are random generated instances (with a backbone). While we have been able to confirm the results (time-to-solution is growing linear with N number of variables), we observed the following:

(+) The (simulated) implemented digital memcomputing machine is capable of solving random instances quite well - independently from the size. We also tested the DMM against a lot of other random instances from previous sat competitions, with similar promising results. The system diverges towards a solution in rapid time. Actually much faster than the original, Matlab based, implementation of the authors.

(-) The authors seem to compare apples with bananas. In our opinion, the DMM should have been tested against YalSat & co, aka other non-complete SAT solvers which have proven to be quite efficient for random instances;

(-) The DMM fails almost entirely against industrial and crafted instances. Similar to other SLS based solvers, the DMM get's stuck in local minima (even the authors claim that that's not the case) forever. Also modifications to the ODE's equations of motion, extensive parameter tuning and using more sophisticated ODE integration schemes (other than forward Euler as suggested by the authors), both explicit and implicit, did not lead the DMM to solve such instances efficiently.

To summarise, the results of the presented DMM (which has been implemented based on the equations of motion as described from the authors here and here) is in line with other Analog inspired computing approaches (f.e. AnalogSAT, Github) and as such can only solve a very specific (and easy) class of problems efficiently (random instances).

Not applicable to real world cases though unfortunately (at least with their equations of motion) and definitely no proof for P=NP (as the authors are not claiming tough).

$\endgroup$
1
  • 1
    $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$
    – Jérémy
    Jul 10 at 9:02
-1
$\begingroup$

Just to add/update to the answer here: (I've removed the previous two answers and repurposed and edited a version I posted on CS stackexchange for this question that should be a better answer. I've also made sure to still address the concerns raised by DanielM as well as a different commenter. Successive edits just became too disorganized and convoluted.)

Scott Aaronson assumed in his 2015 blogpost that a MemComputer is purely an analog machine (which it was in the implementation he talked about) and used a concern that's very valid for analog machines to cast doubt on MemComputing's scalability in general. But the authors of the 2015 paper he talks about are clear that the implementation they were studying as a proof of principle is not unique. They specifically say that digital versions of it are possible. Since a machine with digital input/output doesn't need exponentially increasing precision to extract an output, you can't so easily claim that the exponential was simply moved to frequency space. You could say that simply pointing to a different implementation is a bit cheap, but MemComputing as a concept was built over multiple papers, different papers addressing different things, this one simply didn't attempt to address scalability because it was beyond the scope. This should be possible in research.

The general claim is simply that MemComputers leverage physics to compute in a way similar to quantum computers, except in a non-quantum system that exhibits dynamical long-range order. They do this in the sense that long range correlations (loosely analogous to entanglement) are used to solve hard problems which can be interpreted as having such long-range correlations baked into problem statements. This would simply be a machine that is more expressive than a Turing machine the way some people expect quantum computers to be more expressive than Turing machines. Therefore this would not threaten the generally held conjecture that $P\neq NP$, since that is a statement about Turing machines. Though it would clearly have implications for some versions of the Church-Turing thesis, the same way quantum computers do.

The general principle behind it is the type of dynamical long range order (a kind of collective behavior in physical systems) which has been shown to arise from time non-locality (memory). This is why MemComputing is more than just in-memory computing: it computes with memory as well. The hardware implementation of digital MemComputing machines (DMM), like quantum computers, has not been built in a useful way yet, but should be easier to implement than a quantum computer. DMMs are the most modern instantiations of a MemComputer and are based on self-organizing logic gates. These are (among other desirable aspects) invertible and strongly correlated (due to the memory dynamics) even at large distances. This provides a type of collective behavior which we expect to be more advantageous than mere parallelization.

For more details, see the textbook MemComputing: Fundamentals and Applications, by Di Ventra. This is published by Oxford University Press and is thus peer-reviewed.


More details if needed:

I want to add a couple of paragraphs for those computer scientists whose intellectual alarm bells are probably and understandably ringing right now if they haven't heard of this before.

It is true that MemComputing is perhaps a bit more uncomfortable than quantum computation from a computer science perspective, because in quantum computation, the exponential complexity of NP-complete problems is explicitly moved somewhere: the exponentially increasing Hilbert space which doesn't have to be simulated by a physical quantum computer since that quantum computer just is quantum mechanical to begin with. But MemComputing is really not so different, except that, instead of moving the exponential complexity somewhere explicitly, it addresses the exponential complexity of NP-complete problems more implicitly, by recognizing that NP-complete/NP-hard problems are so difficult precisely because they are often very interconnected. So a physical computer which is similarly interconnected may have an edge. There is, in fact, a deeper reason why MemComputers are so efficient: topology. We use the language of topological field theory to analyze the MemComputing dynamics and find that what drives DMMs towards a solution are instanton states, topological objects that aid the DMM in leveraging "global" information over "local" information in the physical phase space. This also makes DMMs incredibly noise-robust. This topological robustness is, in fact, why some people hope to develop topological quantum computers, since quantum computers are incredibly noise sensitive, hence the difficulty in realizing them.

Another issue is that if MemComputers are classical instead of quantum, then we can simulate these classical systems efficiently on an ordinary computer and let those simulated DMMs solve NP-complete problems for us. Since this constitutes and algorithm on a Turing machine, it would immediately follow that $P=NP$. Yay!

But alas, no. The dynamics of a DMM are governed by non-linear differential equations. These admit chaos and quasi periodic orbits in the physical phase space, which can be a big problem. Luckily, physical DMMs don't admit chaos or quasi-periodic orbits unless a massive amount of noise is dumped on the DMM, which would cause the state of the DMM to become chaotic and preventing it from ever finding a solution more effectively than a random walk. It has been shown that the noise necessary to do this to a physical DMM is equivalent to a temperature which would fry the electronics used to implement the self-organizing logic gates, so that's great. But physical noise enters the dynamics linearly, numerical noise from simulating the DMM very much does not.

So the theorems and studies that make us expect physical DMMs would solve NP-complete problems efficiently don't necessarily hold for simulated DMMs, since those are an entirely different beast to tame. Luckily that doesn't mean simulated DMMs can't be useful. They've been demonstrated to be useful for quantum measurements and the training of some types of neural networks. The company MemComputing Inc. uses simulated DMMs to solve industrial scale NP-complete problems (like shipping, route/schedule optimization for oil rig helicopters, and DoD applications) often by blindly receiving CNF files from them and solving them in 3SAT. This is a bit difficult, since you have to create a model that balances efficiency in simulating the system (getting a reasonably good degree of the polynomial overhead of the simulation) as well as faithfully representing the physics of a MemComputer in a way that's able to solve the type of problem at hand. MemComputing Inc. is a commercial company and therefore bound by NDAs, so unfortunately we don't have insight into their work. But it clearly works in a useful way, otherwise they'd be bankrupt.

Below is a figure of an empirical study on simulated DMMs that used hard instances that were specifically designed as benchmarks for SLS solvers and compares the results to some typical SLSs, including the state of the art SID algorithm.

enter image description here

You can see that in this setting, the DMM can easily solve the hard test instances at multiple 3SAT clause to variable ratios (4.3 being the hardest) and apparently retains the polynomial scalability on these instances (some people might think that these might still be exponentials with small coefficients, but the exponential fits we do for scalability either don't converge or are really bad, while polynomial fits are good fits). It's also worthy to note that the last data-point of the hardest ratio, 4.3, took 15 hours to complete with completely un-optimized, sequential code (other than the optimized hyperparameters of the physical dynamics). Extrapolating from the scalability for the state-of-the-art SID algorithm, it would have taken SID longer than the age of the universe to complete the same data-point.

It is worth stressing that none of this should be taken as some sort of experimental evidence that $P=NP$! There are still very good heuristic and historical reasons to believe $P\neq NP$ and even if that turns out to be false, empirical studies are certainly no way to prove $P=NP$, you need a mathematical proof.

Comment on DanielM's post:

The instances of the above analysis are not easy:

The instances used in the empirical analysis above are not purely random. Barthel instances were specifically designed to be hard benchmark instances for SLS solvers, which is why the paper compared it to some standard SLS algorithms, including the state-of-the-art SID. Barthel instances are "hard" precisely because they are not purely random. They are physics-inspired hard benchmark instances that can be interpreted as physical spin-glasses (notoriously difficult to compute). See the paper Hiding solutions in random satisfiability problems: A statistical mechanics approach, Barthel et al., 2002.

Simulated DMMs can and have been successfully applied to real-world, industrial-scale problems:

MemComputing has been applied to "real world" problems, I've linked peer reviewed examples in quantum measurements and AI in edit 1 above. Even sticking to just 3SAT, the company MemComputing Inc. is solving hard real life problems every day in areas such as shipping as well as route/schedule optimization for oil rig helicopters and more. These are often problems expressed in 3SAT. The company is bound to NDAs since they're a commercial company and we don't have direct insight into their work, but we know they solve these companies' problems by blindly receiving CNF files from them.

Responding to the claim that DanielM's implementation of DMMs gets stuck in local minima like other SLSs:

MemComputing is a unique computational paradigm that needs to be understood physically. If it is not properly understood, there can be problems when you attempt to tinker with the implementation and you could end up eliminating some of its desirable features. We know that the phase space which the DMM explores does not contain local minima, this is by design. What would otherwise be a local minimum is turned into a saddle point by the addition of memory dynamics. We therefore know that the appearance of local minima must be an artifact of implementation. We also know that different methods of integration (like 4th order Runge-Kutta or others) which DanielM mentions are known to introduce ghost critical points. In other words, if you're not careful about which integration scheme you use, you're introducing local minima that the phase space is otherwise guaranteed not to have (this is why the authors suggest Forward Euler, which doesn't cause this issue).

We know about the absence of local minima analytically and by that I mean that the paper on which the above analysis is based (Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing, Bearden et al., 2020) proved it analytically in section VI of the supplemental materials. In fact, many possible concerns are addressed in the supplemental materials of that paper, please scan the titles of those sections for any issues you might have.

Another thing that could've happened with DanielM's implementation is that what he identified as a local minimum due to the program never finishing is actually the DMM entering a chaotic state in which it is effectively lost in phase space (in effect, turning the algorithm into a random walk). With physical noise in a physical MemComputer, it has been shown that it would take a temperature high enough to fry the electronics used to implement the DMM to induce such chaotic states, which are otherwise absent (Critical branching processes in digital memcomputing machines, Bearden et al., 2019). If you're simulating a DMM, you could introduce this with sufficient numerical noise if you're not careful, which would cause abrupt transitions of some of your simulation runs into random-walks.

$\endgroup$
4
  • $\begingroup$ Look at the paper and see for yourself. It's obviously not a proof and perhaps that's ultimately what makes it uninteresting to CS theorists but the computational advantage in the real world is undeniable and it's not just a marginal advantage either. The whole basis of MemComputing is that it re-frames foundational ideas behind practical computation (it's a non-Turing class of computer). So you've got to be a bit more rigorous in your epistemology and not just dismiss it based on Turing-machine-based intuition/theorems/hypotheses. See the textbook MemComputing by Di Ventra for details. $\endgroup$ Jun 20 at 19:55
  • $\begingroup$ "That is poor scholarship." No. Citations exist for a reason. Concepts can be built built over multiple papers. I'll just leave it at this: previous papers, which that paper cites, have addressed issues of scalability, specifically by making the input and output of MemComputers digital. This means that you do not need exponentially increasing precision to extract the solution, for the same reason you don't exponentially increasing precision to extract an output from ordinary computers. $\endgroup$ Jun 20 at 20:04
  • $\begingroup$ I honestly thought thats what my original answer did, but I can edit to clarify. $\endgroup$ Jun 20 at 21:10
  • $\begingroup$ The revision you were looking at happened before our discussion. I posted my edit now. This perhaps won't be fully satisfying, but it's enough to see why Scott's criticism is, at the very least, outdated and why MemComputing is actually quite promising. $\endgroup$ Jun 20 at 22:57

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.