Comments on Computational Complexity: Extreme Oracles

Having now skimmed Lance's paper above, I would li...

2005-08-20T13:56:00.000-05:00

Having now skimmed Lance's paper above, I would like to change my entry to question for Lance.

The paper says, "We however would like to argue that we should never have believed the random oracle hypothesis in the first place." If so, then how should we use oracles to buttress what we believe?

For example, I want to believe that BPP ? BQP. I even want to believe that period-finding (either the Shor or the Simon version) is not in BPP. Should I retreat to a neutral opinion until someone proves that P ? PSPACE? I note that relative to a random oracle, period-finding is not in BPP. Can I interpret this random-oracle result as valid indirect evidence? If not, would some other kind of oracle be better? Or would a collapse result (if BPP = BQP, then some large class = some small class) be better?

I think that it is an important judgement call as ...

2005-08-17T17:23:00.000-05:00

I think that it is an important judgement call as to whether any given oracle is realistic, i.e., that you could hope to imitate it with a language in P or BPP. One famous old construction is that P^PSPACE = NP^PSPACE. But as evidence that P = NP, this is circular: if you believe that PSPACE is a realistic oracle, then you believe a lot more than P = NP.

I think that it was a reasonable hope that random oracles are realistic. Because, to appearances, featureless junk output can be generated in polynmomial time. Despite the result that IP = PSPACE, you could still make a case for realism of random oracles (at least to a bystander like me), because the realism of IP and PSPACE is debatable. (Okay, IP and PSPACE aren't directly realistic. But maybe they admit realistic indirect interpretations.)

This is an important issue in quantum computation. Shor's algorithm actually finds the period of an arbitrary periodic function (which is injective within the period). This gives you an immediate oracle separation between BPP and BQP. How realistic is it? Famously, factoring gives you one realistic imitation of an oracular periodic function. You could speculate that factoring is in BPP, which would make it a poor imitation. But there might still be many other possible imitations.

Wow, Lance, I don't think he was claiming they wer...

2005-08-17T10:45:00.000-05:00

Wow, Lance, I don't think he was claiming they were easy. He was asking how much insight they bring into the unrelativized question. I think there is general agreement that this line of attack turned out to be not as fruitful as it was originally hoped.

If nonrelativizing proofs were so easy, why are th...

2005-08-17T07:20:00.000-05:00

If nonrelativizing proofs were so easy, why are these problems still open?

Check out my survey, The Role of Relativization in Complexity Theory.

In one of your previous posts you mentioned that w...

2005-08-16T22:24:00.000-05:00

In one of your previous posts you mentioned that what you like about TCS is that what we now know will remain true for ever.

How do you feel about these oracle results, especially when considering the IP vs. PSPACE affair? I would think that this should have ended this way of studying complexity classes
as it means that these results essentially don't say anything.

Thanks!

2005-08-16T14:54:00.000-05:00

Thanks!

I added links the the main papers.

2005-08-16T13:49:00.000-05:00

I added links the the main papers.

Is there a good resource for learning what these o...

2005-08-16T11:26:00.000-05:00

Is there a good resource for learning what these oracles are? Or at least pointers to the right papers?