I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will appreciate if someone could shed the light on this topic so that I will be able to continue by myself. Few following sentences are questions and my thoughts about relativization, they will help to navigate the discussion.

Very often relativization comes in comparison with diagonalization, which is a method that helps distinguish between countable set and uncountable set. It somehow comes from relativization that $P$ versus $NP$ question cannot be solved by diagonalization. I don't really see the idea why relativization show the useless of diagonalization, and if it's useless why is actually useless.

The idea behind oracle Turing machine $M^A$ at first is very clear. However, when it comes to $NP^A$ and $P^A$ the intuition disappears. Oracle is a blackbox that is designed for special language and answers the question whether the string on the input of the oracle is in the language in time 1. As I understood TM that contains an oracle is just make some auxiliary operations and ask the oracle. So the core of the TM is the oracle, everything else is less important. What's the difference between $P^A$ and $NP^A$, even thought oracle in both of them works in time 1.

The last thing is the proving the existence of an oracle $B$ such that $P^B \neq NP^B$. I found the proof in several textbooks and in all of them the proof seems very vague. I tried to use "Introduction to complexity" by Sipser, Chapter9. Intractability, and didn't get the idea of construction of a list of all polynomial time oracle TMs $M_i$.

This is more or less everything what I know about relativization, I will appreciate if someonw would decide to share his/her thoughts on the topic.

Addendum: in one of the textbooks I found example of $NP^B$ language (Computational Complexity: A Modern Approach by Boaz Barak Sanjeev Arora. Theorem 3.7. Page 74). $U_B=\left \{ 1^n:some \space string \space of \space length \space n \space is \space in \space B\right \} $ it's unary language. I believe that (1,11,111,1111,...) are all in $U_B$. Author affirms that such a language is in $NP^B$ which is I cannot understand why, hence oracle for B can resolve everything in time 1. Why do we need nondeterministic TM with oracle. If it's not good example of $NP^B$ please put yours such that to approve the existence of $NP^B$.

  • 2
    $\begingroup$ $P^A$ and $NP^A$ are classes of language, they are not Turing machines. You say that the oracle is the "core" of the TM, but that's not necessarily true. For example, what if $A$ is the empty language? $\endgroup$ Commented Nov 14, 2012 at 14:25
  • $\begingroup$ its a very tricky topic generally not so much for undergraduates. one aspect is that oracles are somewhat model dependent. ie there is apparently not a strictly consistent way to devise oracles. the basic intuition is that its a machine with a "magical" subroutine capability (given by the oracle) such that the machine + oracle is always at least as powerful as the original machine, but sometimes not significantly more powerful... $\endgroup$
    – vzn
    Commented Nov 14, 2012 at 15:57
  • 1
    $\begingroup$ related question: cs.stackexchange.com/questions/1271/…, with a great answer from Tsuyoshi Ito $\endgroup$
    – A.Schulz
    Commented Nov 15, 2012 at 6:53
  • $\begingroup$ I am not sure what you are asking. You seem to be confused about the BGS proof and also ask a bunch of other questions. Please ask a single focused question. Note that this is not a discussion board or forum, it is a Q&A site. $\endgroup$
    – Kaveh
    Commented Nov 17, 2012 at 23:31
  • $\begingroup$ Are you asking for an explaination of BGS proof for existence of an oracle that separates P and NP? Are you asking for an explanation about the relation of relativization and diagonalization? (if so, does Tsuyoshi's answer in the lined question answer your question? if not please explain why not.) $\endgroup$
    – Kaveh
    Commented Nov 17, 2012 at 23:34

1 Answer 1


You haven't really asked any question, but it seems like you don't know what $\rm{P}^A$ means and what $\rm{NP}^A$ means for a language $A$. The class $\rm{NP}^A$ is simply all languages that are decidable in "NP time", given a turing machine with $A$ as an oracle. This means a non-deterministic turing machine with access to $A$ which runs in polynomial time. The $\rm{P}^A$ is the deterministic version.

  • 1
    $\begingroup$ Thank you very much for the answer, could you give example how the power of NTM with oracle helps us recognize more language than DTM with oracle. BGS proof shows such language but I didn't get the proof. $\endgroup$
    – com
    Commented Nov 18, 2012 at 4:28
  • $\begingroup$ Sometimes, instead of a language $A$, I find some complexity class, for example $P^{NP}$, what does that mean in this case? That we choose $A$ to be an NP-complete? (more generally, that we choose a langauge that is complete for the class $A$)? $\endgroup$
    – FNH
    Commented Jan 16, 2017 at 2:29
  • $\begingroup$ Yes, $P^{NP}$ is indeed $P$ with an NP-complete problem as an oracle. $\endgroup$ Commented Jan 16, 2017 at 22:50

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.