3 ms·

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

by 33a 12y ago

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

JacobEdelman 12y ago
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.
- 33a 12y ago
  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.)
  - halcy 12y ago
    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.

by 33a 12y ago

JacobEdelman 12y ago

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.

33a 12y ago
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.)
- halcy 12y ago
  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.