Re:Predicting When P=NP Is Resolved
by pwdisswordfish2 on Monday December 23, 2019 @01:39AM
(#21861891)
P^O is always a subset of NP^O, whatever the O.
Re:Predicting When P=NP Is Resolved
by joe_the_user on Monday December 23, 2019 @02:23AM
(#21862022)
I think the gp left out the strict before the later subset statements.
Re:Predicting When P=NP Is Resolved
by someguy12342 on Monday December 23, 2019 @02:47AM
(#21862099)
That's right! I completely flubbed that part while doing some other edits! Thanks. What I wanted to say is there are O1 and O2 such that:
P^O1 strict subset NP^O1
and
P^O2 equals NP^O2
A strict subset B
they also show
A^O strict subset B^O
for ANY oracle O. Most of these proofs don't actually explicitly state this is true, but they are readily to be extended this way (e.g. the diagonlizing proofs of the time hierarchy theorem)
However, we know (Baker, Gill, Solovay) that there exists and oracle O1 where
P^O1 subset NP^O1
as well as an oracle O2 such that
P^O2 not subset NP^O2
Therefore, we know we a proof of P != NP must not relativize or else that would contradict the aforementioned result.