3 ms·
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
by 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 agoThat'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 agoIf 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.