3 ms·
On a slightly pedantic note, even if the mixing operation were truly constant time, it would have no impact on P?=NP. There is no reason to believe that all com
by benchaney 10y ago
On a slightly pedantic note, even if the mixing operation were truly constant time, it would have no impact on P?=NP. There is no reason to believe that all computers that can be physically constructed are deterministic.
- jepler 10y agoA physically-realizable system for solving problems that are NP in polynomial time, mass and energy would be very economically interesting, just as quantum computers are for Shor's algorithm and simulated annealing. (despite the fact that we can't yet perform Shor's algorithm at scale and at as far as I know some people still raise doubts about whether D-Wave's product truly outperforms computational simulated annealing or truly does anything "quantum") It also gives us insights into one of the other interesting questions of our day: Is simulating a physical system of polynomial size in P, or not in P? If you find that polynomial-size physical systems can solve problems in NP but believe that P≠NP, then you would also believe simulation is not in P.
- benchaney 10y agoAbsolutely. I didn't mean to imply it wouldn't be interesting. It just wouldn't have any impact on the question of P vs NP from a logocal perspective. Also, with respect to your physical system argument, I'm not sure I agree. Any computer that actually exists has some probability of making a computation error. With that in mind, simulating a physical system with a step that involves becoming a physical system is likely not a valid argument from an algorothmic reduction point of view.