I recently found out a surprising fact from this paper by Scott Aaronson. P=NP does not (given current results) imply that P=BQP. That is, even if P=NP there may still be substantial speedups from quantum computing. This result was surprising to me, since for most computational classes we normally think about that are a little larger than P, they end up equaling P if P=NP. This is due to the collapse of the polynomial hierarchy. Since we cannot resolve that BQP lives in the polynomial hierarchy, we can’t make that sort of argument.
Sure, but that’s just saying that P=NP is not a robust hypothesis. Conditional on P=NP, what odds do you put that P is not P^#P or PSPACE? (though maybe the first is a robust hypothesis that doesn’t cover BQP)
Conditional on P=NP, what odds do you put that P is not P^#P or PSPACE? (though maybe the first is a robust hypothesis that doesn’t cover BQP)
I’m not sure. If P=NP this means I’m drastically wrong about a lot of my estimates. Estimating how one would update conditioning on a low probability event is difficult because it means there will be something really surprising happening, so I’d have to look at how we proved that P=NP to see what the surprise ended up being. But, if that does turn out to be the case, I’m fairly confident I’d then assign a pretty high probability to P=PSPACE. On the other hand we know that of the inequalities between P, NP, PSPACE and EXP, at least one of them needs to be strict. So why should I then expect it to be strict on that end? Maybe I should then believe that PSPACE=EXP? PSPACE feels closer to P than to EXP but that’s just a rough feeling, and we’re operating under the hypothetical that we find out that a major intuition in this area is wrong.
I recently found out a surprising fact from this paper by Scott Aaronson. P=NP does not (given current results) imply that P=BQP. That is, even if P=NP there may still be substantial speedups from quantum computing. This result was surprising to me, since for most computational classes we normally think about that are a little larger than P, they end up equaling P if P=NP. This is due to the collapse of the polynomial hierarchy. Since we cannot resolve that BQP lives in the polynomial hierarchy, we can’t make that sort of argument.
Sure, but that’s just saying that P=NP is not a robust hypothesis. Conditional on P=NP, what odds do you put that P is not P^#P or PSPACE? (though maybe the first is a robust hypothesis that doesn’t cover BQP)
I’m not sure. If P=NP this means I’m drastically wrong about a lot of my estimates. Estimating how one would update conditioning on a low probability event is difficult because it means there will be something really surprising happening, so I’d have to look at how we proved that P=NP to see what the surprise ended up being. But, if that does turn out to be the case, I’m fairly confident I’d then assign a pretty high probability to P=PSPACE. On the other hand we know that of the inequalities between P, NP, PSPACE and EXP, at least one of them needs to be strict. So why should I then expect it to be strict on that end? Maybe I should then believe that PSPACE=EXP? PSPACE feels closer to P than to EXP but that’s just a rough feeling, and we’re operating under the hypothetical that we find out that a major intuition in this area is wrong.