Skip to main content
MathOverflow

Return to Answer

deleted 150 characters in body
Source Link
user36212
user36212
  • 1.7k
  • 14
  • 14

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$ is essentially the same as P (there are more languages, but any language in $P^A$ differs in finitely many places from a language in P) so in particular A isdoes not incontain $P^A$$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.

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$ is essentially the same as P (there are more languages, but any language in $P^A$ differs in finitely many places from a language in P) so in particular A is not in $P^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.

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.

Source Link
user36212
user36212
  • 1.7k
  • 14
  • 14

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$ is essentially the same as P (there are more languages, but any language in $P^A$ differs in finitely many places from a language in P) so in particular A is not in $P^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.