4 ms·
On a related note, anyone know anything about this company? http://memcpu.com/ http://memcpu.com/ They claim to be able to solve NP-complete problems with pol
by colordrops 9y ago
On a related note, anyone know anything about this company?
http://memcpu.com/ 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.
- ikeboy 9y agohttps://www.scottaaronson.com/blog/?p=2212 https://www.scottaaronson.com/blog/?p=2212 tl;dr It's crap
- ollin 9y agoFrom Scott Aaronson's "Memrefuting" post (https://www.scottaaronson.com/blog/?p=2212 https://www.scottaaronson.com/blog/?p=2212): > 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.
- mcguire 9y agoOne of their publications: "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)." http://aip.scitation.org/doi/abs/10.1063/1.4975761?journalCode=cha http://aip.scitation.org/doi/abs/10.1063/1.4975761?journalCo... 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. A part of another abstract of one of their other papers (http://ieeexplore.ieee.org/document/7924376/?reload=true http://ieeexplore.ieee.org/document/7924376/?reload=true) is, "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.
- nenreme 9y agoFrom 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.
- mikeash 9y agoCan't a Turing machine emulate a digital circuit in polynomial time? Then either they've proven that P=NP, or they're full of it.
- colordrops 9y agoSupposedly it's analog, but the Aaronson article linked by others gets into why that doesn't help either.
- mikeash 9y agoI 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.
- pavel_lishin 9y ago> They claim to be able to solve NP-complete problems with polynomial resources using non-Turing architectures. Not sure why you'd sell that technology, instead of using it to effectively and invisibly conquer the world.