# Intuition behind Relativization

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$.

• $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? Nov 14 '12 at 14:25
• 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...
– vzn
Nov 14 '12 at 15:57
• related question: cs.stackexchange.com/questions/1271/…, with a great answer from Tsuyoshi Ito Nov 15 '12 at 6:53
• 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. Nov 17 '12 at 23:31
• 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.) Nov 17 '12 at 23:34

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.
• 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$)? Jan 16 '17 at 2:29
• Yes, $P^{NP}$ is indeed $P$ with an NP-complete problem as an oracle. Jan 16 '17 at 22:50