Tuesday, May 26, 2009

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.

12 comments:

  1. Aren't circuit lower bounds non-relativizing?

    ReplyDelete
  2. what circuit lower bounds ?

    ReplyDelete
  3. We're always eager to produce a new result
    Even if an oracle we must consult

    For though P=NP is ever open
    To solve it we're still hopin'

    And though exponential search we despise
    We're not afraid to relativize

    For we will never weary
    Of computer science theory

    Conference on Computational Complexity Theory
    March 1983
    Santa Barbara, California

    ReplyDelete
  4. I guess should have said, I have some issues with oracle results. Sorry for "hate"...rjlipton

    ReplyDelete
  5. "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."

    There are only two alternations because the polynomial hierarchy collapses to the second level if P=NP. Or am I wrong?

    ReplyDelete
  6. There is a better phrase that both of you might even agree on:

    "I am frustrated by oracle results."

    ReplyDelete
  7. Anon 3.45: If P=NP, the entire polynomial hierarchy collapses to P. But this just tells us that a constant number of alternations is no better than no alternations at all. PSPACE involves _polynomially_ many alternations (in particular, the number of alternations depends on the input length), and it is not at all clear if these alternations can be eliminated.

    ReplyDelete
  8. There do exist results that do not relativize, and do not use interactive proofs. (I was surprised no one else posted this.) How about the result that Time(f) \subset Space(f/log f)? Someone else mentioned circuit lower bounds. For other examples see here.

    It's the same in cryptography: people claim (or used to claim) that black-box separations rule out "known techniques" but there are non black-box constructions.

    As for Lipton's post, I think his main point was that relativization is not useful because it is hard to tell whether a proof technique relativizes or not.

    ReplyDelete
  9. Another example: the PPST'83 result

    NTIME[n] != DTIME[n]

    does not relativize. One constructs an oracle A whereby x is in A if and only if x is a yes-instance for the bounded halting problem on nondeterministic machines with oracle A. See

    http://pages.cs.wisc.edu/~dieter/Courses/2007s-CS810/Scribes/PS/lecture04.ps

    ReplyDelete
  10. is P^PSPACE = PSPACE?

    ReplyDelete
  11. is P with an oracle to PSPACE equal to PSPACE, the answer seems yes.

    ReplyDelete