4
$\begingroup$

My question is about why does the result of Baker-Gill-Solovay not prove that $P \neq NP$. There have been several questions on this forum about this topic perhaps but I couldn't find my specific question amongst them.

Context: This is what I had in mind when I first saw the Baker-Gill-Solovay result (there exists an oracle $A$ such that $P^A \neq NP^A$): I will try to give a proof for $P \neq NP$. Suppose $P=NP$ then $P^A = NP^A$ for all oracles $A$. By Baker-Gill-Solovay result we arrive at a contradiction. When I asked my prof about this he said that the implication $P=NP \implies P^A = NP^A$ is wrong. So I wanted to check why (and where) does it fail.

I think it is correct that $P \subseteq NP \implies P^A \subseteq NP^A$ for all oracles $A$ because any poly-time TM with oracle access to $A$, is also a poly-time NDTM with oracle access to $A$.

My question is: Why (if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$) is false?


My reasoning would go as follows: $NP \subseteq P$ means that given any NDTM (which involves a guessing sequence, followed by a poly-time verification), I can replace the guessing sequence with some poly-time TM. But given a NDTM with oracle access to $A$, I cannot directly replace the guessing sequence with some poly-time TM (as per the hypothesis), because in this NDTM, the guessing sequence might involve the access to oracle $A$.

Following that, I want to argue why isn't it so, that given a NDTM with oracle access to $A$, I can move all these calls to oracle $A$, after the guessing sequence? That is to say - why couldn't I, using non-determinism, guess the answers to my oracle queries and in the final step, verify these particular guesses using actual oracle queries?


More precisely, can I not re-define the definition of $L \in NP^A$ as follows: there exists a poly-time TM $M$ and a polynomial $p$ such that $x \in L \iff \exists w$ such that $|w| \leq p(|x|)$ and $M^A(x,w) = 1$?

Apologies for being too vague in my arguments above but I have just started learning Complexity Theory.

Edit1: Changed the question from given a oracle $A$, if $NP \subseteq P$ then $NP^A \subseteq P^A$ to if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$

Edit2: My definitions are: $P^A$ is the set of languages decided by a poly-time TM with oracle access to $A$ and $NP^A$ is the set of languages decided by a poly-time NDTM with oracle access to $A$

Edit3: Added more context to the problem.

$\endgroup$
  • $\begingroup$ Are you sure it is false? $NP \subseteq P$ implies that $NP = P$ which in turn indeed implies that $NP^A \subseteq P^A$. $\endgroup$ – prime_hit May 14 at 11:47
  • $\begingroup$ Why does $P=NP$ implies $NP^A \subseteq P^A$? ($IP =PSPACE$ but there is an oracle which separates them) $\endgroup$ – kishlaya May 14 at 12:16
  • 1
    $\begingroup$ @prime_hit It is false and you are making a common error: assuming that $NP^A$ is a function of $NP$. In fact, it is a different complexity class, where the $^A$ modifies the description of $NP$, not $NP$ itself. For a concrete counterexample, it is actually known that $IP = PSPACE$, but $IP^A \ne PSPACE^A$ for some oracles $A$. $\endgroup$ – 6005 May 14 at 12:36
3
$\begingroup$

Your statement holds for all oracles $A$ iff $\mathsf{P} \neq \mathsf{NP}$. Indeed, if $\mathsf{P} \neq \mathsf{NP}$ then your statement vacuously holds. Conversely, if $\mathsf{P} = \mathsf{NP}$, then your statement fails for a random oracle $O$, since such an oracle satisfies $\mathsf{P}^O \neq \mathsf{NP}^O$ almost surely.

A similar argument shows that if $A$ is a $\mathsf{PSPACE}$-complete language then your statement holds, since in that case $\mathsf{P}^A = \mathsf{NP}^A$ is known to hold.

The proof that $\mathsf{P} \subseteq \mathsf{NP}$ relativizes, which means that it works even in the presence of an oracle. That is, the proof only uses arguments that keep holding even when the Turing machines are allowed access to an oracle. In all other cases, you cannot conclude from a statement of the form $\mathsf{A} \subseteq \mathsf{B}$ that $\mathsf{A}^O \subseteq \mathsf{B}^O$ for all oracles $O$. The two statements are about two different objects: the first one is about Turing machines without oracle access, and the second one is about Turing machines with oracle access to $O$.

This actually happens in practice, as mentioned in the comments: $\mathsf{IP}=\mathsf{PSPACE}$, but there are oracles $O$ relative to which $\mathsf{IP}^O \neq \mathsf{PSPACE}^O$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. I still have a little doubt which I think I couldn't explain in my post: "Either $P \neq NP$ or $P=NP$. If it's the former then I rest my case. So suppose $P=NP$. Then it would mean given any oracle $A$, $P^A = NP^A$. But this contradicts the random oracle separation result". Surely I have made a mistake somewhere. Where did my argument go wrong? $P=NP \implies P^A=NP^A$ is wrong argument. So I was trying to understand what is wrong with this, which I elaborated upon in my post. $\endgroup$ – kishlaya May 14 at 12:45
  • $\begingroup$ If $\mathsf{P} = \mathsf{NP}$ then it doesn't mean that $\mathsf{P}^A = \mathsf{NP}^A$. Indeed, if $A$ is a random oracle then the second statement won't hold. You cannot "raise both sides to the power $A$". You should think of the statement $\mathsf{P} = \mathsf{NP}$ as the same as $\mathsf{P}^\emptyset = \mathsf{NP}^\emptyset$. It's just a particular oracle. Equality for one oracle doesn't imply equality for all oracles. $\endgroup$ – Yuval Filmus May 14 at 12:47
  • $\begingroup$ Exactly! $P=NP$ doesn't mean $P^A = NP^A$. I understand they are different objects as you said. But... I am trying to understand why does it fail? So let me please argue this way: Assume $P=NP$ and fix an oracle $A$ which separates $P$ and $NP$. It would still be true that $P^A \subseteq NP^A$ (as I said in my post). And so it means $NP^A \subseteq P^A$ is false. Why? This is what I have tried to reason about - but failed. $\endgroup$ – kishlaya May 14 at 12:59
  • $\begingroup$ If you tried to write a complete formal argument, one of the steps will be wrong. I don't see such an argument in the question, only some ideas. $\endgroup$ – Yuval Filmus May 14 at 13:01
  • 1
    $\begingroup$ I think your definition is the usual one. $\endgroup$ – Yuval Filmus May 14 at 13:10

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.