Right. You’re definitely gonna be able to get the same solution to the same problem twice as fast. The thing labeled by labels like “NP hard” is that doubling your hardware doesn’t let you solve problems that are twice as complicated in your unit of time. So your dumb robot can do dumb things twice as fast, but it can’t do things twice as smart :P
There’s one more consideration, which is that if you’re approximating and you keep the problem the same, doubling your hardware won’t always let you find a solution that’s twice as good. But I think this can reasonably be either sublinear or superlinear, until you get up to really large amounts of computing power.
Right. You’re definitely gonna be able to get the same solution to the same problem twice as fast. The thing labeled by labels like “NP hard” is that doubling your hardware doesn’t let you solve problems that are twice as complicated in your unit of time. So your dumb robot can do dumb things twice as fast, but it can’t do things twice as smart :P
There’s one more consideration, which is that if you’re approximating and you keep the problem the same, doubling your hardware won’t always let you find a solution that’s twice as good. But I think this can reasonably be either sublinear or superlinear, until you get up to really large amounts of computing power.