[Computational Complexity] Oracle Results are Good For You
- For a short time in the 70's, some believed that oracle results would lead to true independence results in computational complexity. Richard Lipton in his post I Hate Oracle Results bemoans the fact that oracles haven't lived up to this hype. But "Hate" is an awfully strong word to apply to one of the most powerful tools in computational complexity.Let me illustrate by an example. Consider the following open problem:
Does P=NP imply P=PSPACE?Here's an approach: Chandra, Kozen and Stockmeyer characterized PSPACE by alternating polynomial time and one could possibly use the P=NP assumption to eliminate those alternations one at a time.This approach doesn't work and in fact no similar approach can work. How do I know that? Because of the following relativization result due to Ker-I Ko.
There is an oracle A such that PA=NPA≠PSPACEA.If you are an oracle-naysayer, Ko's result shouldn't stop you from working on the problem. Let's try non-relativizing techniques. The tools of interactive proofs don't seem to work here. How about other non-relativizing techniques? We don't have any other non-relativizing techniques. CKS is nearly 30 years old, Ko's oracle is 20 years old and this problem remains completely open.There are hundreds of like problems which we cannot settle with non-relativizing techniques. If you feel oracle results no longer play a major role in computational complexity than we should have been able to settle scores of these problems. But in fact we have only twice proven a result in computational complexity when there was a previously known oracle going the other way, both directly related to interactive proofs.I agree with Lipton that it would be nice to have a formal logical characterization of a "relativizing technique" but just because we don't doesn't mean oracle results don't properly guide our research efforts. More from my 1994 relativization manifesto that I still stand by today.
Posted By Lance to Computational Complexity at 5/26/2009 10:41:00 AM