Re: Significance of "Relativizations of the P =? NP Question"

In article <1137942430.592765.122510@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<examachine@xxxxxxxxx> wrote:
>Could you please tell me a bit about this paper? What does it imply
>for a potential solution?

I assume you mean the paper by Baker, Gill, and Solovay. This shows that
there's an oracle X with respect to which P^X = NP^X, and there's another
oracle Y with respect to which P^Y != NP^Y.

Most proofs in complexity theory---let's take P != EXPTIME as an
example---can easily be relativized. That is, you can easily modify
the proof to show that P^X = EXPTIME^X for *any* oracle X.

The Baker-Gill-Solovay result shows that any proof of P != NP cannot
relativize. Therefore, when you're trying to construct a proof of P != NP,
you should ask yourself, "What happens when I try to relativize this proof?
Where does it break down?" If there isn't any step in your proof that
resists relativization, then your proof can't possibly work.

The most famous examples of proofs in complexity theory that don't
relativize come from the area of interactive proofs. For example, Shamir
proved that IP = PSPACE, even though there is an oracle that separates the
two. There is some debate as to "which step" of the proof is the one that
can't be relativized. It is an interesting open problem to define precisely
what a "relativization of a *proof*" (as opposed to a single statement like
P = NP) means. It's clear in specific examples what it means, but a
satisfactory general theory is lacking.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: Significance of "Relativizations of the P =? NP Question"
    ... > oracle Y with respect to which P^Y!= NP^Y. ... "What happens when I try to relativize this proof? ... It is interesting that you say a general theory is lacking. ... I was once thinking about whether a diagonalization proof was possible, ...
    (comp.theory)
  • question on relativization of an algorithm
    ... "It is a misnomer to relativize a complexity class C. ... criteria for C applied to the machines using the oracle A." ... Is it a language associated ...
    (comp.theory)