Comment by 33a | Hacker News Reader

Comment by 33a | Hacker News Reader

Parent Full thread

I still don't fully understand what they mean by a "memcomputer" here, but if you take a boring old real RAM computer + floor function you can even solve all of PSPACE in polynomial time:

http://dl.acm.org/citation.cfm?id=682381

Regarding models like FPGAs, etc., these can all be simulated on boring old Turing machines with at most a polynomial time overhead, so it probably isn't what they are talking about here. It seems like they have some mixed analog digital model of a computer here, but the details are a bit obtuse. It wouldn't really surprise me if they were solving NP-hard problems given that regular old real arithmetic + thresholding /rounding can lead to some crazy behaviors.

I'd agree except for this bit:"ndeed, a practical implementation of a UMM can already be accomplished by using memelements such as memristors, memcapacitors or meminductors, although the concept can be implemented with any system with memory, whether passive or active. For instance, in this work we have proposed a simple topologically-specific architecture that, if realized in hardware, can solve the subset-sum problem in just one step with a linear number of memprocessors" That seems to be pretty suspicious to me.

That's true. It might be that under some theoretical assumptions their model could actually solve an instance of an NP-hard problem, but it could also be that the physical realization doesn't scale.

They report solutions for a few small cases of subset sum, I would be more interested to see it run on something with say a few thousand variables.

(After all similar claims have been made about other analog systems, like soap bubbles, etc.)

If I understand correctly, that would be under the theoretical assumption that you can perform computations on numbers that require infinitely many bits (or at least, likely, exponentially many bits) to represent in constant time, which is an assumption that you are not just generally allowed to make.

Reply on news.ycombinator.com