I don’t understand why you think new physics is required to solve hard instances of NP-complete problems. We routinely solve the hard instances of NP-hard problems in practice on computers—just not on large instances of the problem.
Eliezer already conceded that trivial instances of such problems can be solved. (We can assume that before he made that concession he thought it went without saying.)
New physics might be required to solve those problems quickly, but if you are willing to wait exponentially long, you can solve the problems just fine.
The physics and engineering required to last sufficiently long may be challenging. I hear it gets harder to power computers once the stars have long since burned out. As far as I know the physics isn’t settled yet.
(In other words, I am suggesting that “just fine” is an something of an overstatement when it comes to solving seriously difficult problems by brute force.)
The physics and engineering required to last sufficiently long may be challenging. I hear it gets harder to power computers once the stars have long since burned out. As far as I know the physics isn’t settled yet.
That counterargument is a bit too general, since it applies not only to NP problems, but even to P problems (such as deciding whether a number is the GCD of two other numbers), or even any arbitrary algorithm modified by a few lines of codes such that its result is unaffected, merely delayed until after the stars burned out, or whatever limit we postulate.
For NP problems and e.g. P problems both, given how we understand the universe, there is only a finite number of inputs in both cases which are tractable, and an infinite number of inputs which aren’t. Though the finite number is well different for both, as a fraction of all “possible”, or rather well-defined (let’s avoid that ambiguity cliff) inputs, it would be the same.
Cue “We all live in a Finite State Machine, Finite State Machine, Finite State Machine …”
Eliezer already conceded that trivial instances of such problems can be solved. (We can assume that before he made that concession he thought it went without saying.)
The point can’t be confined to “trivial instances”. For any NP-complete problem on some reasonable computing platform that can solve small instances quickly, there will be instance sizes that are non-trivial (take appreciable time to solve) but do not require eons to solve. There is absolutely no mathematical reason for assuming that for “natural” NP-complete problems, interesting-sized instances can’t be solved on a timescale of months/years/centuries by natural processes.
The dichotomy between “trivial” and “impossible to solve in a useful time-frame” is a false one.
Eliezer already conceded that trivial instances of such problems can be solved. (We can assume that before he made that concession he thought it went without saying.)
The physics and engineering required to last sufficiently long may be challenging. I hear it gets harder to power computers once the stars have long since burned out. As far as I know the physics isn’t settled yet.
(In other words, I am suggesting that “just fine” is an something of an overstatement when it comes to solving seriously difficult problems by brute force.)
That counterargument is a bit too general, since it applies not only to NP problems, but even to P problems (such as deciding whether a number is the GCD of two other numbers), or even any arbitrary algorithm modified by a few lines of codes such that its result is unaffected, merely delayed until after the stars burned out, or whatever limit we postulate.
For NP problems and e.g. P problems both, given how we understand the universe, there is only a finite number of inputs in both cases which are tractable, and an infinite number of inputs which aren’t. Though the finite number is well different for both, as a fraction of all “possible”, or rather well-defined (let’s avoid that ambiguity cliff) inputs, it would be the same.
Cue “We all live in a Finite State Machine, Finite State Machine, Finite State Machine …”
The point can’t be confined to “trivial instances”. For any NP-complete problem on some reasonable computing platform that can solve small instances quickly, there will be instance sizes that are non-trivial (take appreciable time to solve) but do not require eons to solve. There is absolutely no mathematical reason for assuming that for “natural” NP-complete problems, interesting-sized instances can’t be solved on a timescale of months/years/centuries by natural processes.
The dichotomy between “trivial” and “impossible to solve in a useful time-frame” is a false one.