Problem Detail: 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 Bright } $ 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$.
Asked By : com
Answered By : Pål GD
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6665
