Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
As I understand, diagonalization cannot be used to prove or disprove P vs NP, because for some oracle $A$, $P^A = NP^A$, whereas under another oracle $B$, $P^B \neq NP^B$.
I don't fully understand this logic. Diagnolization (Time Hierarchy Theorem) proves that $P \neq EXPTIME$. Does it therefore mean that there is no oracle $X$ that could ever make $P^X = EXPTIME^X$ ?
First let me try to be a bit more precise about your first sentence. The reasoning you list shows that no relativizing proof can prove or disprove P=NP. "Diagonalization" is a fuzzy concept, and depending on what you mean by it, might or might not relativize -- diagonalization proofs tend to relativize, but no guarantees. So the oracle result rules out some/many kinds of diagonalization proofs, but maybe not all. See, e.g., https://cstheory.stackexchange.com/q/6575/5038.
Second, let's discuss your final question. Yes, it is indeed true that $P^X \ne EXPTIME^X$ for all $X$; there is no oracle $X$ that will make them equal. I'll talk through why that is. The standard way to prove $P \ne EXPTIME$ is to prove $TIME(p(n)) \ne TIME(p(n)^2)$ (the time hierarchy theorem), then notice that this implies $P \ne EXPTIME$ (since $TIME(2^n) \ne TIME(2^{2n})$, but $P \subseteq TIME(2^n)$ and $TIME(2^{2n}) \subseteq EXPTIME$). The proof of $TIME(p(n)) \ne TIME(p(n)^2)$ uses diagonalization. This proof does indeed relativize. In particular, for all oracles $X$, we do indeed have $TIME^X(p(n)) \ne TIME^X(p(n)^2)$. It follows that, for all oracles $X$, we have $P^X \ne EXPTIME^X$ (by the same argument as before).
See also: https://cstheory.stackexchange.com/q/8902/5038, https://cstheory.stackexchange.com/q/6575/5038.
The time hierarchy theorem relativizes, meaning that it also holds in the oracle Turing machine model. Intuitively, the diagonalization proof of the time hierarchy theorem only uses the fact that we can encode Turing machines as strings and have the ability to simulate some machine given its encoding. These properties also hold when we proceed to talk about the relativized (oracle) world.
In the P vs NP case however, one cannot hope for a relativizing proof, since we know that the answer depends on the oracle. Thus, a black box treatment of the oracle Turing machine would not be enough here.
