Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
2  
$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? –  Yuval Filmus 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
1  
related question: cs.stackexchange.com/questions/1271/…, with a great answer from Tsuyoshi Ito –  A.Schulz 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. –  Kaveh 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.) –  Kaveh Nov 17 '12 at 23:34
show 1 more comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  fog Nov 18 '12 at 4:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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