f



why does relativization not imply P!=NP??

hi all, this question occured to me about 2 yrs
ago and it also popped up again recently on a mailing
list I founded/moderate, theory-edge,

http://groups.yahoo.com/group/theory-edge/

BGS75 proved that there are oracles such that
P and NP have "contradictory relativizations" as it has
been called in the literature, ie two oracles X,Y exist such that

P^X == NP^X and P^Y != NP^Y

the "proof" that P!=NP based on this 
was reposted by nexus-scorpion as follows,
can anyone tell me what is wrong with it?

> Theorem:
> If A and B are complexity classes such that there exists an 
> oracle X such that A^X != B^X, then A != B. Hence P != NP by the 
> results of BGS75.
>
> Proof:
> Consider the contrapositive:
> "If A = B, then there does not exist an oracle X such that A^X != B^X."
>
> If the hypothesis is true, and A = B, then for any oracle X, A^X 
> and B^X are the same object, and hence A^X == B^X for all oracles X. 
> Therefore it is impossible to choose an oracle X such that A^X != 
> B^X. i.e. the implication is true whenever the hypothesis is true. 
> Therefore the Theorem is true. Hence P != NP.

if there is something wrong with this "proof" as presumably there
is, can someone restate the correct related conjecture on oracles that
would lead to a P!=NP proof?

also, some people are asserting to me that 

if A != B then A^X != B^X [1]

for all oracles X follows by the (hartmanis) time hierarchy theorem. 

but I havent seen this proven anywhere in
the literature, although it does seem to have been claimed by some
authors. yet we have a result by chang and others for diagonalization
proofs and complexity class separations that have contradictory
relativizations. 

in fact I am starting to doubt the above [1] and I wonder if
(conjecture)

two classes have contradictory relativizations iff they are unequal....?

are there any hardcore algorithmic theorists who can address this?
I posted this conjecture a few years ago on theory-edge and
also algorithm-forge iirc.
0
vznuri (44)
7/2/2003 9:53:40 PM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

4 Replies
385 Views

Similar Articles

[PageSpeed] 15

vznuri@yahoo.com (V.Z.Nuri) wrote in message news:<1e0fd315.0307021353.559befa7@posting.google.com>...
> 
> > If A and B are complexity classes such that there exists an 
> > oracle X such that A^X != B^X, then A != B. Hence P != NP by the 
> > results of BGS75.
> >
> > Proof:
> > Consider the contrapositive:
> > "If A = B, then there does not exist an oracle X such that A^X != B^X."
> >
> > If the hypothesis is true, and A = B, then for any oracle X, A^X 
> > and B^X are the same object, and hence A^X == B^X for all oracles X. 
> > Therefore it is impossible to choose an oracle X such that A^X != 
> > B^X. i.e. the implication is true whenever the hypothesis is true. 
> > Therefore the Theorem is true. Hence P != NP.
> 
> if there is something wrong with this "proof" as presumably there
> is, can someone restate the correct related conjecture on oracles that
> would lead to a P!=NP proof?

Hi,

The fact that A=B does not imply that A^X=B^X.
As an example consider the classes PSPACE and IP which are known
to coincide (by Shamir's result), yet there is an oracle relative to which
IP^X does not even contain co-NP (Fortnow and Sipser 88).
Actually this is even true for a random oracle, as proved by Chang
et al. "The random oracle hypothesis is wrong".

So if you think about it, giving an oracle to an interactive proof system
is not really the same as giving an oracle to a polynomial space bounded
machine.



HK
0
klauck (2)
7/3/2003 4:12:16 AM
In article <1e0fd315.0307021353.559befa7@posting.google.com>,
V.Z.Nuri <vznuri@yahoo.com> wrote:
>> If the hypothesis is true, and A = B, then for any oracle X, A^X 
>> and B^X are the same object

No, that's not true.  A and B are typically families of languages decided by
certain classes of machines; A^X and B^X aren't defined by taking A and B
"directly" (so to speak) and doing something to them, but are defined by
taking the classes of machines and adding the same oracle.  There's no
guarantee that the new classes of machines will decide the same languages.

>also, some people are asserting to me that 
>if A != B then A^X != B^X [1]
>for all oracles X follows by the (hartmanis) time hierarchy theorem. 

For arbitrary A and B this isn't true.  Taking the contrapositive, we get:
"If A^X = B^X for some oracle X then A = B."  When A = P and B = NP we know
that the hypothesis is true, but we don't know that P = NP.  Perhaps the
assertion was made in a context where A and B were limited to a specific
type of complexity class?
-- 
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
0
tchow (869)
7/3/2003 12:47:54 PM
<tchow@lsa.umich.edu> wrote in message
news:3f0425fa$0$3930$b45e6eb0@senator-bedfellow.mit.edu...
> In article <1e0fd315.0307021353.559befa7@posting.google.com>,
> V.Z.Nuri <vznuri@yahoo.com> wrote:
> >> If the hypothesis is true, and A = B, then for any oracle X, A^X
> >> and B^X are the same object
>
> No, that's not true.  A and B are typically families of languages decided
by
> certain classes of machines; A^X and B^X aren't defined by taking A and B
> "directly" (so to speak) and doing something to them, but are defined by
> taking the classes of machines and adding the same oracle.  There's no
> guarantee that the new classes of machines will decide the same languages.
>
> >also, some people are asserting to me that
> >if A != B then A^X != B^X [1]
> >for all oracles X follows by the (hartmanis) time hierarchy theorem.
>
> For arbitrary A and B this isn't true.  Taking the contrapositive, we get:
> "If A^X = B^X for some oracle X then A = B."  When A = P and B = NP we
know
> that the hypothesis is true, but we don't know that P = NP.  Perhaps the
> assertion was made in a context where A and B were limited to a specific
> type of complexity class?

Yes, it was made only with respect to P and EXP.



l8r, Mike N. Christoff



0
mchristoff (248)
7/3/2003 5:25:45 PM
I missed a couple of questions the first time...

In article <1e0fd315.0307021353.559befa7@posting.google.com>,
V.Z.Nuri <vznuri@yahoo.com> wrote:
>if there is something wrong with this "proof" as presumably there
>is, can someone restate the correct related conjecture on oracles that
>would lead to a P!=NP proof?

I don't think there is any "conjecture on oracles" (that anyone believes,
anyway) that implies P != NP, but this could just be ignorance on my part.
The random oracle hypothesis was perhaps a candidate before it was shot
down.

>(conjecture)
>two classes have contradictory relativizations iff they are unequal....?

If I recall correctly, IP and PSPACE admit contradictory relativizations,
but IP = PSPACE.
-- 
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
0
tchow (869)
7/3/2003 5:53:28 PM
Reply: