I don't understand the notion of relativization. I expose with an example. Consider a class $A$ that contains $P$, e.g. $NP$. Why $P^A$ is not necessarily equal to $A$? I can naively think that if one can decide any problem in $A$, one can also decide any problem that uses polynomially many steps in a Turing machine plus calls to $A$. One can have at most polynomially many calls to $A$, thus $P^A$ seems there is only a polynomial overhead compare to $A$. If $A$ is $NP$, I could give a certification for all the (polinomially many) oracle calls, and also easily give a certification of the polynomial rest of the computation. I understand that if it is true, then $NP$ is the same as $coNP$, both being contained in $P^{NP}$ from the polynomial hierarchy. So, where is the error in my naive argument?

  • $\begingroup$ Perhaps your source of confusion is that $P$ is defined to be the class of languages decided by deterministic polynomial time Turing machines, not the class of languages decided in polynomial time by "arbitrary machines". When you add an oracle to a polynomial-time Turing machine $M$, you get a machine $M'$ that is no more a "deterministic polynomial time Turing machine". In order to prove that $M'$ is in $P$ (or more formally that $M'$ decides a language in $P$), you must give an equivalent deterministic polynomial time TM $M''$ (with no oracles) that decides the same language of $M'$. $\endgroup$ – Vor May 26 '15 at 19:12

Take $A=NP$, as you requested. $P^{NP}$ is not necessarily equal to $NP$.

Let me give an example why not. Consider TAUTOLOGY (given a boolean formula $\varphi$, is it true for all possible assignments to the variables?). TAUTOLOGY is known to be co-NP-complete. Therefore, TAUTOLOGY most likely is not in NP, since if TAUTOLOGY were in NP, it would follow that NP = co-NP, which is widely suspected not to be the case.

However, TAUTOLOGY is certainly in $P^{NP}$. Here's why. Given an oracle for SAT, we can solve TAUTOLOGY as follows: query whether $\varphi$ is in SAT; then flip the answer (if $\varphi$ is in SAT, answer "no, $\varphi$ is not in TAUTOLOGY"; if $\varphi$ is not in SAT, answer "yes, $\varphi$ is in TAUTOLOGY"). This shows how to solve TAUTOLOGY in polynomial time given an oracle for SAT, and SAT is in NP, so this shows that TAUTOLOGY is in $P^{NP}$.

So TAUTOLOGY is an example of a problem that is in $P^{NP}$, but probably isn't in NP (unless NP = co-NP). Hopefully this helps illustrate why NP is not the same as $P^{NP}$.

If not, here's a little more intuition. NP is a particular class. $P^{NP}$ is the class of problems that can be solved by querying an oracle for NP, possibly many times. The "many times" part is the key difference between NP and $P^{NP}$. A (many-one) reduction between two NP problems can only query a NP-oracle once, while $P^{NP}$ allows you to query the oracle as many times as you like. That seems to be a lot more powerful, and it's the reason why $P^{NP}$ seems to be a bigger class than NP.

  • $\begingroup$ Thanks for the answer but it is not the answer I was looking for. My tentative intuition was the same you gave: in P^NP I can query the NP oracle many time. But it is not convincing because in P^NP I can query at most polynomially many times the NP oracles, thus providing at most a polynomial overhead of complexity with respect to NP which does not really separate the two classes. Am I mistaken? In your example there is only one query to SAT, so it doesn't clarify the intuition. $\endgroup$ – neophyte Jan 27 '15 at 10:10
  • $\begingroup$ Moreover, even if I tend to believe all these conjectures, like NP is different from co-NP, these are still conjectures and do not provide a proof. $\endgroup$ – neophyte Jan 27 '15 at 10:13
  • $\begingroup$ @neophyte, of course it's not going to provide an unqualified proof. Asking for an unqualified proof (with no unproved assumptions) is unreasonable. If the polynomial hierarchy collapses, then $P^{NP} = NP$. It's conjectured that the polynomial hierarchy doesn't collapse, but that's not known for sure. Therefore there's no hope of an unqualified proof that $P^{NP} \ne NP$. $\endgroup$ – D.W. Jan 27 '15 at 21:20
  • $\begingroup$ ok, but you haven't replied to my criticism on your intuition. can you, please? $\endgroup$ – neophyte Feb 2 '15 at 9:02

Why might $P^A$ not equal to $A$?

$A$ might be weaker than $P$

$P^A$ can't be weaker than $P$, but $A$ might be. For example, if $A$ is the complexity class of linear-time problems $O(n)$ then $P^A = P^{O(n)}=P$.

$A$ might have different strengths than $P$

For example, consider $B=O(1)^{3SAT}$ and $A=3Coloring$. The only problem $A$ can solve is 3-coloring. It can't solve 3-Sat. $B$ can solve 3-sat, and various constant time problems, but it can't solve 3-coloring because it doesn't have enough time to do so directly or to translate the problem into 3-sat.

On the other hand, $B^A = {O(1)^{3SAT}}^{3Coloring}$ can solve both 3-sat and 3-coloring, so it's stronger than either $A$ or $B$ individually.

In the case of $P$, a class with different strengths could be the class of problems that takes $O(n)$ space. Some problems in $P$ require more-than-linear space, and some problems that require $O(n)$ space use exponential time. So $P^{O(n) space}$ gains both the powers of $P$ and $O(n) space$, making it larger than either of them individually.

$A$ and $P$ might synergize into something better

For example, $P^{NP}$ can trivially solve $coNP$ problems, but it's suspected that $P \subset coNP$ and $NP \neq coNP$ and $(P \cup coNP) \not \subset coNP$.

This is even more striking if you think of it as $NP^{NP}$. Complexity classes don't have to be low for themselves.


Your Answer

