4 ms·
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
by 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 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.