They claim to be able to solve NP-complete problems with polynomial resources using non-Turing architectures. I'd normally call them crackpots but they have serious pedrigree and have been published in Science and Nature. I'm still very skeptical, but don't have the chops to evaluate their caims.
> all proposals along these lines simply “smuggle the exponentiality” somewhere that isn’t being explicitly considered, exactly like all proposals for perpetual-motion machines smuggle the entropy increase somewhere that isn’t being explicitly considered. The problem isn’t a practical one; it’s one of principle.
I see. The page mentions "digital" a few times, but I guess they're either only referring to part of the machine, or are using the term unconventionally.
"Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines
"We introduce a class of digital machines, we name Digital Memcomputing Machines, (DMMs) able to solve a wide range of problems including Non-deterministic Polynomial (NP) ones with polynomial resources (in time, space, and energy)."
The actual paper is behind a paywall. I am not Scott Aaronson. I probably could not reasonably evaluate their claims even if I could read them. But Aaronson has somewhere posted a list of the weird things that would happen if you could solve an NP-complete problem in polynomial time, and that list provides a good reason to believe you can't.
"Our method can be extended efficiently to any level of precision, since we prove that producing n-bit precision in the output requires extending the circuit by at most n bits. This type of numerical inversion can be implemented by DMM units in hardware; it is scalable, and thus of great benefit to any real-time computing application."
Which makes me suspect there are hard limits on the size of the problems their "hardware" can handle.
But it's fun to chase the graph thingys around on their home page.
From the first paper that you linked (available freely on sci-hub) it looks like they were unable to proove that their method actually works. They made simulations with small problems but are not sure if this method will work for larger problems.
http://memcpu.com/
They claim to be able to solve NP-complete problems with polynomial resources using non-Turing architectures. I'd normally call them crackpots but they have serious pedrigree and have been published in Science and Nature. I'm still very skeptical, but don't have the chops to evaluate their caims.