In Impagliazzo's imaginary world Heuristica, P ≠ NP but all NP problems are easy on average for any samplable probability distribution.

In Impagliazzo's paper, he implies that if you do manage to find a hard instance in Heuristica, it won't take much more effort to solve the instance than it took to find the instance in the first place.

In this world, Grouse might be able to find problems that Gauss cannot answer in class, but it might take Grouse a week to find a problem that Gauss could not solve in a day, and a year to find one that Gauss could not solve in a month. (Here, I am assuming that Gauss has some polynomial advantage over Grouse, since Gauss is after all a genius!) Presumably, “real-life” is not so adversarial that it would solve intractable problems just to give us a hard time, so for all practical purposes this world is indistinguishable from Algorithmica.

However, what I'm not clear on is whether the following scenario is possible: It takes time 1.001n to find a 3-SAT instance that takes time 1.3n to solve. In other words, Grouse can still maintain an exponential advantage over Gauss provided that Grouse is prepared to invest an exponential amount of work.

Is there a simple argument (or if not, is there a standard complexity hypothesis) that implies that this can't happen in Heuristica?

| cite | improve this question | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.