2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 10 at 7:42
  • $\begingroup$ Are you aware of this relevant question? $\endgroup$ – Yuval Filmus Sep 10 at 7:43
  • $\begingroup$ 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. $\endgroup$ – Newberry Sep 10 at 22:34
  • $\begingroup$ Arora-Barak might contain a proof, though I doubt you will find it easier to follow. $\endgroup$ – Yuval Filmus Sep 10 at 22:35
2
$\begingroup$

Let me answer your concrete questions:

  • An oracle is a language. One way to describe a language is to give a procedure for constructing it.
  • The construction is not a counterexample to P=NP. It shows that there exists an oracle relative to which P and NP are different. It also gives another oracle relative to which they are the same. Later, it was shown that P is different from NP relative to a random oracle (almost surely); recently this was extended to the entire polynomial hierarchy. The modern interpretation of such results is that diagonalizing techniques (techniques that would also work relative to an arbitrary oracle) cannot be used to settle the P vs NP question.
  • "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$.
  • Your final question is a bit specific. I suggest trying to read the proof again, and if you fail, check a more modern account. Note that the result can be proved in several ways, so a proof appearing in a different source might be different.
$\endgroup$
  • $\begingroup$ There is a sentence in the proof: "P_i^B(i) can ask at most p_i(n) questions." It implies that P_i^B(i) calls B(i) multiple times? Each time with a different string of length n from the canonical enumeration of strings? [There are more strings of length n than p_i(n).] $\endgroup$ – Newberry Sep 11 at 16:01
  • $\begingroup$ en.wikipedia.org/wiki/Oracle_machine $\endgroup$ – Yuval Filmus Sep 11 at 16:28
  • $\begingroup$ I think we are talking at cross-purposes. $\endgroup$ – Newberry Sep 12 at 16:11
  • $\begingroup$ $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. $\endgroup$ – Yuval Filmus Sep 12 at 16:25
  • 1
    $\begingroup$ $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. $\endgroup$ – Yuval Filmus Sep 13 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.