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?


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

  • $\begingroup$ Sorry, can you be more specific. What do you mean with you don't have enough time to ask the oracle? $\endgroup$ – user11502 Dec 11 '10 at 11:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Stefan Geschke Dec 11 '10 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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