New answers tagged

1

A proof relativizes if every step in the proof relativizes. You should go over your proof, and check whether each step remains valid in the presence of an oracle. In contrast, a result relativizes by definition if it still holds relative to an arbitrary oracle. Hence, to show that a result doesn't relativize, all you have to do is give an oracle with ...


3

Your statement holds for all oracles $A$ iff $\mathsf{P} \neq \mathsf{NP}$. Indeed, if $\mathsf{P} \neq \mathsf{NP}$ then your statement vacuously holds. Conversely, if $\mathsf{P} = \mathsf{NP}$, then your statement fails for a random oracle $O$, since such an oracle satisfies $\mathsf{P}^O \neq \mathsf{NP}^O$ almost surely. A similar argument shows that ...


Top 50 recent answers are included