21
$\begingroup$

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.

When I learnt to the topic of relativization and oracle machines, I read the following theorem:

There exist oracles A, B such that $P^A = NP^A$ and $P^B \neq NP^B$.

And then the book said because of this, we can't solve the problem of NP = P by using relativization. But I think what it implies is that $NP \neq P$. The reasoning is like this:

First of all, it is quite easy to see that:

$$A = B \Leftrightarrow \forall \text{oracle O, }A^O = B^O$$

Though I think it is obvious, I still give a proof to it:

A simple proof of NP != P ?

And the negation of it is:

$$A \neq B \Leftrightarrow \exists \text{oracle O such that } A^O \neq B^O$$

Therefore since there is an oracle B such that:

$$ NP^B \neq P^B$$

we can conclude that $ NP \neq P $

What's the problem with the above reasoning?

$\endgroup$
1
  • $\begingroup$ related: 1, 2 and 3 $\endgroup$ Feb 25, 2018 at 13:35

5 Answers 5

23
$\begingroup$

The map $A \to A^O$ does not depend only on the elements contained in the language $O$, so it is not an operation on languages. It depends on the semantic way in which the language $A$ is defined. For instance, $NP^O$ is allowed both nondeterminism and access to $O$. $P^O$ is allowed deterministic polynomial time and access to $O$. I believe it is true that $BPP$ can be separated from $P$, even though it is thought that $BPP = P$.

$\endgroup$
6
  • 3
    $\begingroup$ +1. Akhil, I think this is exactly right. The notion of $\Gamma^O$ for an arbitrary class $\Gamma$ of languages seems to be incoherent. $\endgroup$ Aug 15, 2010 at 22:56
  • 1
    $\begingroup$ I'm confused by your last sentence since I can't fit it with the rest of your reply. Given that it talks about relativisation, do you mean that BPP can be separated from P given some oracle? Thanks! $\endgroup$
    – Opt
    Aug 16, 2010 at 2:38
  • $\begingroup$ Correct. This is the reference from the Complexity zoo: [BF99] H. Buhrman and L. Fortnow. One-sided versus two-sided randomness, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 100-109, 1999. people.cs.uchicago.edu/~fortnow/papers/rpvsbpp.ps $\endgroup$ Aug 16, 2010 at 6:26
  • 2
    $\begingroup$ Yes, and it gets worse. When you move to relativizations of space-bounded complexity classes, there are multiple possible ways of defining oracle access: do we allow the oracle tape to be write-only so that queries can exceed the space bound, or not? The choice affects what you can separate and collapse using oracles. A sampling of these headaches can be found in Ruzzo, Simon, Tompa: "Space-Bounded Hierarchies and Probabilistic Computations" (1984) and papers that cite them. This is one reason why it's unclear what relativization barriers say about space lower bounds. $\endgroup$ Aug 18, 2010 at 0:36
  • 1
    $\begingroup$ Yes, I forever lament (and I think many others do too) that the notation for oracles in complexity theory is very broken and confusing. (Ilya gives the canonical example of this, regarding IP and PSPACE.) As others are saying here, you actually define oracles relative to a machine class (i.e., model of computation), not relative to languages or complexity classes. Let's not even get started on the meaning of relativization with respect to promise problems... $\endgroup$ Dec 19, 2014 at 8:50
27
$\begingroup$

The statement $A = B \rightarrow \forall O \; A^O = B^O$ is incorrect. For example, it is known that $\mathrm{IP} = \mathrm{PSPACE}$, but we know that there exists an oracle $A$ such that $\mathrm{IP}^A \ne \mathrm{PSPACE}^A$.

Direct substituion does not work here, because different characterisations of one particular class can behave different when we relativize them.

$\endgroup$
5
  • 3
    $\begingroup$ Here's a reference: portal.acm.org/citation.cfm?id=49327 This paper shows that co-NP does not have interactive proofs. $\endgroup$ Aug 15, 2010 at 16:23
  • 2
    $\begingroup$ Doesn't that contradict co-NP $\subseteq$ PSPACE = IP ? $\endgroup$
    – user5810
    Aug 15, 2010 at 18:38
  • 1
    $\begingroup$ @Ricky - The abstract states that there exists an oracle relative to which co-NP does not have interactive proofs. Since IP^A \neq PSPACE ^A for some oracle A, everything works out. $\endgroup$
    – Opt
    Aug 15, 2010 at 19:00
  • 2
    $\begingroup$ Then Suresh should have said ""co-NP has interactive proofs" does not relativize". $\endgroup$
    – user5810
    Aug 15, 2010 at 19:08
  • 1
    $\begingroup$ my mistake. Ricky is indeed correct. $\endgroup$ Aug 16, 2010 at 6:28
25
$\begingroup$

The others have pointed out the flaw in your suggested argument, but let me discuss something from the first part of your post.

The conclusion of the Baker-Gill-Solovay relativization result (that there are oracles $A$ and $B$ for which $P^A=NP^A$ and $P^B\neq NP^B$) isn't that "we can't solve the problem of NP=P by relativization," as you say, but rather something more profound: the conclusion is that we cannot solve the NP=P problem by any method that admits of relativization. This is an enormous class of methods, which includes all of the standard powerful methods of computability theory. The reason is that if we could prove $P=NP$ or $P\neq NP$ using methods that can accommodate oracles, then we would immediately deduce the corresponding equality or inequality for all oracles, in contradiction to the Baker-Gill-Solovay result.

The significance of this is that since all the standard methods do admit relativization, we will not be able to settle P versus NP using only those methods; we must be more imaginative and subtle.

That is, the point isn't that the theorem rules out the one method of relativization as a method of solving P versus NP, but rather that it rules out all methods that accommodate relativization. Since this includes most of our methods, it is a serious obstacle.

$\endgroup$
12
$\begingroup$

I was holding off on posting a non-answer, but am encouraged by JDH.

There's still something deeply puzzling about the idea that if $A = B$, there's possibly an oracle for which $A^O \ne B^O$, and that seems to be at the heart of the OP question. In that respect, ilyaraj's example of IP and PSPACE is actually better, because unlike with P and NP, where we don't know the true answer, we actually KNOW that IP = PSPACE, and yet there's still an oracle that separates them.

But I think a deeper explanation needs to go beyond relativization, to the properties that relativization relies on. The Arora-Barak book explains this quite well: they point out that proofs like diagonalization rely on efficient simulation (universality) and the ability to list out machines (enumeration), and that any oracle-based result relies ONLY on these two properties.

Thus, the real answer to why P vs NP is independent of relativized arguments is that you need to exploit more information than just universality and enumeration. This comes to mind precisely because of the "new" barrier coming out the Deolalikar proof discussions, that proof techniques that try to differentiate the geometry of solutions to SAT vs P-time problems can't work.

$\endgroup$
1
  • 7
    $\begingroup$ My 2 cents: The way I think of the this is that although A and B are equal, they might have different oracle access mechanisms. If A is allowed to interact with an oracle in a weak way while B can interact in a very powerful way, then it is reasonable that A^O cannot solve all the problems that B^O can, since O is not helping A as much as it is helping B. $\endgroup$ Aug 16, 2010 at 5:38
5
$\begingroup$

And of course, this is exactly what happens in the $\mathrm{IP}^A \ne \mathrm{PSPACE}^A$ proof -- IP is defined by its access to outside information, which can be considered akin to an oracle -- while PSPACE does not. In the most cursory sense, both the IP-verifier and the IP-prover have access to an oracle of random bits. PSPACE-bound machines in general do not. A cursory way of looking at this, without even reference to the proof (which frankly I forget) is that granting IP an oracle of random bits would by definition do noting to it. But granting PSPACE an oracle of random bits could improve its computational ability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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