|
2 | added 3 characters in body | ||
|
My question is the following: Can a (probabilistic, deterministic, ndtm) oracle turing machine $A$ calling an oracle lying residing in a superior (more difficult) complexity class $B$, have less power then the oracle called ($A^B < 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 |
|
||
weaker oracle machine ?My question is the following: Can a (probabilistic, deterministic, ndtm) oracle turing machine $A$ calling an oracle lying in a superior (more difficult) complexity class $B$, have less power then the oracle called ($A^B < 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?
|
||||
