How am I supposed to read the P=?NP relativization proof? I am reading the classical paper Relativization of the P=?NP problem by Baker, Gill and Solovay, in particular the proof that there exist an oracle $$B$$ such that $$\mathsf{P}^B \neq \mathsf{NP}^B$$ on page 436. I have some questions and your help will be appreciated.

• The procedure does not seem to be an oracle but a deterministic algorithm.

• Is this construction a counterexample to P = NP?

• What does this mean "Run query machine $$P_i$$ with oracle $$B_i$$ on input $$x_i = 0^n$$?" Does it mean that $$P_i$$ asks

1. if $$B_i$$ accepts $$0^n$$
2. if $$B_i$$ accepts any string of length $$n$$
3. ONE BY ONE if $$B_i$$ accepts a string of length $$n$$ from the canonical enumeration?
• I assume that the set $$B$$ or $$B_i$$ is initially empty. Does it mean that the FIRST string of length $$n$$ from the canonical enumeration will always be added?

• You are supposed to pick up a modern account of the diagonalization barrier. There are several textbooks, online lecture notes and even blogs covering it. – Yuval Filmus Sep 10 at 7:42
• Are you aware of this relevant question? – Yuval Filmus Sep 10 at 7:43
• Any suggestions for modern accounts? I know there is a "randomized" version, which is easier technically, but I understand it even less conceptually. Anyway, I am trying to understand the idea of the original proof. – Newberry Sep 10 at 22:34
• Arora-Barak might contain a proof, though I doubt you will find it easier to follow. – Yuval Filmus Sep 10 at 22:35

• "Run query machine $$P_i$$ with oracle $$B_i$$ on input $$x_i = 0^n$$" has the following meaning. The machine $$P_i$$ is an oracle machine — it is a Turing machine that has a special mechanism allowing it to access the oracle. We run $$P_i$$ on the input $$0^n$$, i.e., the string of length $$n$$ consisting entirely of zeroes. Whenever $$P_i$$ makes an oracle access, we answer according to $$B_i$$.
• $P_i$ is an oracle machine. Make sure you understand how these operate. Also, I don't really see where the canonical enumeration of strings comes from. – Yuval Filmus Sep 12 at 16:25
• $P_i$ is an oracle machine. Without understanding oracle machines, you don’t even understand the theorems being proven, let alone the proofs. Once you understand how oracle machines operate, you will be able to answer such questions on your own. – Yuval Filmus Sep 13 at 19:20