# weaker oracle machine ?

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?

## 1 Answer

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

• 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
• 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