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.
Aren't circuit lower bounds non-relativizing?
ReplyDeletewhat circuit lower bounds ?
ReplyDeleteWe're always eager to produce a new result
ReplyDeleteEven 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
I guess should have said, I have some issues with oracle results. Sorry for "hate"...rjlipton
ReplyDelete"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."
ReplyDeleteThere are only two alternations because the polynomial hierarchy collapses to the second level if P=NP. Or am I wrong?
There is a better phrase that both of you might even agree on:
ReplyDelete"I am frustrated by oracle results."
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.
ReplyDeleteThank you, Lance.
ReplyDeleteThere 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.
ReplyDeleteIt'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.
Another example: the PPST'83 result
ReplyDeleteNTIME[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
is P^PSPACE = PSPACE?
ReplyDeleteis P with an oracle to PSPACE equal to PSPACE, the answer seems yes.
ReplyDelete