Return to Revisions

Suppose that $A$ is an oracle; then it is standard to write $\mathsf{P}^A$ for the complexity class $\mathsf{P}$ relativized to $A$. As I have mentioned elsewhere on MO, this is incredibly confusing notation. It can lead to the following spurious argument that has confused generations of students. Assume that $\mathsf{P}=\mathsf{NP}$. Then for all oracles $A$, $\mathsf{P}^A=\mathsf{NP}^A$. But by Baker–Gill–Solovay, we know that there exists an oracle $A$ such that $\mathsf{P}^A\ne \mathsf{NP}^A$. This is a contradiction. Hence $\mathsf{P}\ne \mathsf{NP}$.