Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

My question is the following:

Can a (probabilistic, deterministic, ndtm) oracle turing machine $A$ calling an oracle residing in a superior (more difficult) complexity class $B$, have less power then the oracle called ($A^B < B$).
My believe is that this new class should be at least as powerful as $B$?

For example, assuming that i've $P^X$, where $X$ resides in a superior complexity class.

Could $P^X$ be weaker than $X$ in some cases and, if yes, is a meaningful complexity class?

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

If you think of Turing machines that have an additional oracle tape and the complexity class $C$ under consideration is below linear time, then for any nontrivial oracle $X$ we have $X\not\in C^X$, just because you don't have enough time to actually ask the oracle.
In all other cases (i.e., if you allow for linear time computations), you will have $X\in C^X$, witnessed by the machine that takes a natural number $n$ as an input and then goes to the $n$-th cell in the oracle tape and checks whether this contain 0 or 1 (or "yes" or "no" or whatever).

share|improve this answer
    
Sorry, can you be more specific. What do you mean with you don't have enough time to ask the oracle? –  user11502 Dec 11 '10 at 11:41
1  
On input $n$ it takes time $n$ to access the $n$-th cell on the oracle tape. If your complexity class is something like logarithmic time, then your machine is required to give an answer to a query in time $c\cdot\log n$, where $n$ is the size of the input (I am assuming that you code input $n$ by a string of $1$'s of length $n$. If you insist on the usual binary coding, replace log by loglog for the argument). Now if $n$ is sufficiently large, then the time $n$ that you need to access the $n$-th cell of the tape is bigger than the time $c\cdot\log n$ that the machine can use. –  Stefan Geschke Dec 11 '10 at 12:02
    
Thanks for the comprehensive response. –  user11502 Dec 12 '10 at 12:43
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.