3 ms·
Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show A st
by someguy12342 7y ago
Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show
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.
- pwdisswordfish2 7y agoP^O is always a subset of NP^O, whatever the O.
- joe_the_user 7y agoI think the gp left out the strict before the later subset statements.
- someguy12342 7y agoThat'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