Welcome to MathOverflow

Question

0

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?

edited Dec 11 2010 at 9:43

asked Dec 11 2010 at 9:34

unknown (google)
3●2

Stefan Geschke · Accepted Answer · 2010-12-11 10:39:49Z UTC

4

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

answered Dec 11 2010 at 10:39

Stefan Geschke
10.6k●1●14●37

Sorry, can you be more specific. What do you mean with you don't have enough time to ask the oracle? – unknown (google) Dec 11 2010 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 2010 at 12:02

Thanks for the comprehensive response. – unknown (google) Dec 12 2010 at 12:43

weaker oracle machine ?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.