most recent 30 from http://mathoverflow.net 2013-05-23T10:48:16Z http://mathoverflow.net/feeds/question/49034 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49034/weaker-oracle-machine unknown (google) 2010-12-11T09:34:24Z 2010-12-11T10:39:49Z

<p>My question is the following:</p> <p>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 &lt; B$). <br> My believe is that this new class should be at least as powerful as $B$?</p> <p>For example, assuming that i've $P^X$, where $X$ resides in a superior complexity class.</p> <p>Could $P^X$ be weaker than $X$ in some cases and, if yes, is a meaningful complexity class?</p>

http://mathoverflow.net/questions/49034/weaker-oracle-machine/49036#49036 Stefan Geschke 2010-12-11T10:39:49Z 2010-12-11T10:39:49Z

<p>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.<br> 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).</p>