Baker, Gill, Solovay - Relativization [closed]

Question

How am I supposed to read the P=?NP relativization proof? I am reading

Theodore Baker, John Gill, and Robert Solovay. Relativization of the P=?NP problem. Siam Journal of Computing, 4:432-442, 1975 [219]

in particular the proof that there exist an oracle B such that P^B = NP^B on page 436. I have some questions and your help will be appreciated.

• Why do the authors use "B" interchangeably a) for the oracle and b) for a set of strings? Machine P_i calls oracle B to construct set B?

• 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

a) if B_i accepts 0^n b) if B_i accepts any string of lenght n c) ONE BY ONE if B_i accepts a string of length n from the canonical enumeration?

• I assume that the set B/B_i is initially empty. Does it mean that the FIRST string of length n form the canonical enumeration will always be added?

PSEUDOCODE

Enum[n,j] = j-th string of length n in a canonical enumeration

P_i(n) = i + n^i

BEGIN: CONSTRUCTION OF SET B i := 0 n_i := 0

LOOP | Obtain n > n_i such that P_i(n) < 2^n | | j := 0 // index in canonical enumeration | LOOP | | IF Oracle_B_i(Enum[n,j]) accepts THEN | | | EXIT LOOP and do nothing | | END_IF | | | | j := j+1 | | | | IF j > P_i(n) THEN // At most P_i(n) questions | | | Add Enum[n,j] to B[i] | | | EXIT LOOP | | END_IF | END_OF_LOOP | | i := i+1, | n_i := 2^n END_OF_LOOP END

Answer 1

There are better expositions of this than the original paper..!

(1) An oracle for a decision problem is essentially the same thing as a set of strings. To see this, observe that all you need to know to have the oracle is the set of strings for which the oracle will output True.

(3) This doesn't provide any input on whether P is NP or not. This is an example of pervasive bad notation. P and NP (like most mathematical objects) have a literal (extensional) and descriptive (intensional) existence, and we usually think of these as being the same, except when we cannot as here. $P$ and $NP$ are (literally) both a collection of languages, so you check $P=NP$ by seeing if every language is either in both or not in both. Literally, you cannot write down the set $P$ as it is infinite. But $P$ and $NP$ are (descriptively) given by some agreed-on finite definition; you can write down the description of $P$ (and I assume you know what this is). Annoyingly, the operation ^B acts on the description of $P$ (and of $NP$) not on the literal set.

So what BGS prove is that there are two sets $P^B$ and $NP^B$, related to $P$ and $NP$ by changing the description of these sets in a certain well-defined way, which happen to be equal. (And they also, separately, prove there are two sets $P^A$ and $NP^A$ which are not equal.)

(2) The best way to get to (this) BGS proof is to begin from Savitch's Theorem that PSPACE=NPSPACE. Proof: It's trivial that PSPACE is a subset of NPSPACE (because a deterministic TM is a non-deterministic TM which happens always to jump to its next state in a set of size one). So the question is why any given NPSPACE language L can be decided by a deterministic TM in polynomial space. The answer to this is to give a deterministic algorithm which does this job. To do this, take an NTM M which decides L in polynomial space. For convenience, assume M never attempts to use more than a given polynomial $f(n)$ space on input of length $n$ (you can assume this by modifying any given machine to count its memory usage and halt with failure at the memory limit; this doesn't affect the property of being a polynomial-space deciding machine for L). Now a given x in L is accepted by M if and only if there is a path in the configuration graph (nodes record all possible tape+position+state information, directed edges for possible jumps of M) from (x,0,initial state) to any node with the accepting state. And there is a deterministic algorithm which can check exactly this in polynomial space (not the same polynomial $f$, but related).

Once you know Savitch's Theorem (and that PSPACE has complete problems, which is fairly easy), this part of BGS is almost trivial. If your oracle B is a decision algorithm for a PSPACE-complete problem, then $P^B$ is clearly in PSPACE and also by definition of completeness is equal to PSPACE. And NP^B is trivially a superset of this, and clearly in NPSPACE, so it must also be PSPACE.

The other part (construct A such that $P^A$ is not $NP^A$) is much easier; take one random string of each length $n$. (or, if you prefer, one of Kolmogorov complexity tending to infinity) and it is easy to show $P^A$ does not contain $A$. But $A$ is in $NP^A$, the point being that nondeterminism allows for guessing the element in $A$, so these two classes are different.