3 ms·

A lot of machines that purport to solve an NP-hard problem in a short period of time have some trick that makes them impractical, like requiring the ability to

A lot of machines that purport to solve an NP-hard problem in a short period of time have some trick that makes them impractical, like requiring the ability to reduce the noise floor in a signal exponentially or pump an exponential amount of energy into a system. Has it been shown that such physical resources are more-or-less interchangeable with running time for the purposes of complexity theory?

ScottAaronson 8y ago
No, I think this is more a question for physics than for complexity theory -- complexity theory basically just takes the computational model and the resources you care about as inputs, then uses math to study how much of the resources are inherently required to solve a given problem. Absent an ultimate theory of fundamental physics, we're unlikely to have a full answer to your question -- e.g., to be able definitively to rule out the possibility of "hypercomputers" solving NP-hard problems in polynomial time. What we can do is (1) to explain the failure (often, the forehead-bangingly obvious, don't-point-to-the-exponential-elephant-in-the-room failure) of all EXISTING proposals along these lines, and (2) to point to deep discoveries in fundamental physics -- most notably, the Bekenstein bound https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound -- which seem to constrain any future quantum theory of gravity to have a form that would rule out these sorts of hypercomputers (for example, by limiting the amount of energy that can be pumped into a finite region, without causing the region to collapse to a black hole, and by likewise ruling out computer components that are smaller than 1 Planck length across or that do more than 1 step per Planck time). I've often speculated that ultimately, the hardness of NP-complete problems in the physical world might come to be seen as analogous to the impossibility of faster-than-light signalling or perpetual motion machines---i.e., something that we simply take as primitive and then use to explain other phenomena in physics. But while the hardness of NP-complete problems sometimes gets used in that way already, I also think we have a lot more work to do before the situations are truly parallel. (For starters, we could prove P!=NP. :-) )

ScottAaronson 8y ago

No, I think this is more a question for physics than for complexity theory -- complexity theory basically just takes the computational model and the resources you care about as inputs, then uses math to study how much of the resources are inherently required to solve a given problem. Absent an ultimate theory of fundamental physics, we're unlikely to have a full answer to your question -- e.g., to be able definitively to rule out the possibility of "hypercomputers" solving NP-hard problems in polynomial time. What we can do is (1) to explain the failure (often, the forehead-bangingly obvious, don't-point-to-the-exponential-elephant-in-the-room failure) of all EXISTING proposals along these lines, and (2) to point to deep discoveries in fundamental physics -- most notably, the Bekenstein bound https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound -- which seem to constrain any future quantum theory of gravity to have a form that would rule out these sorts of hypercomputers (for example, by limiting the amount of energy that can be pumped into a finite region, without causing the region to collapse to a black hole, and by likewise ruling out computer components that are smaller than 1 Planck length across or that do more than 1 step per Planck time). I've often speculated that ultimately, the hardness of NP-complete problems in the physical world might come to be seen as analogous to the impossibility of faster-than-light signalling or perpetual motion machines---i.e., something that we simply take as primitive and then use to explain other phenomena in physics. But while the hardness of NP-complete problems sometimes gets used in that way already, I also think we have a lot more work to do before the situations are truly parallel. (For starters, we could prove P!=NP. :-) )