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.
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.
