debugMinor
Machine with an oracle for a language that cannot decide another language in polynomial time
Viewed 0 times
cannotpolynomialwithtimelanguagethatfordecideanothermachine
Problem
We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$.
However, there is any explicit example of two languages $A$ and $B$ such that $P^A\not\subseteq P^B$ and $P^A\not\supseteq P^B$?
I was thinking in something like $\mbox{HALT}$ and $\mbox{EMPTY}$ but Yuval Filmus made me see that in fact $P^{\mbox{HALT}} \subseteq P^{\mbox{EMPTY}}$, because $\mbox{EMPTY}$ is stronger than $\mbox{HALT}$. Nevertheless is possible to find an explicit language satisfying the desired property? What about $\mbox{FINITE}=\{: L(M) \mbox{ is finite}\}$, it can be compared with $\mbox{HALT}$ in the same way as $\mbox{EMPTY}$?
However, there is any explicit example of two languages $A$ and $B$ such that $P^A\not\subseteq P^B$ and $P^A\not\supseteq P^B$?
I was thinking in something like $\mbox{HALT}$ and $\mbox{EMPTY}$ but Yuval Filmus made me see that in fact $P^{\mbox{HALT}} \subseteq P^{\mbox{EMPTY}}$, because $\mbox{EMPTY}$ is stronger than $\mbox{HALT}$. Nevertheless is possible to find an explicit language satisfying the desired property? What about $\mbox{FINITE}=\{: L(M) \mbox{ is finite}\}$, it can be compared with $\mbox{HALT}$ in the same way as $\mbox{EMPTY}$?
Solution
Let $A,B$ be two incomparable Turing degrees (these can be constructed by diagonalization, known in this context as forcing). If $P^A \subseteq P^B$ then in particular $A \in P^B$, and so $A$ reduces to $B$; since we know this is impossible, we can conclude that $P^A \nsubseteq P^B$. Similarly $P^A \nsupseteq P^B$.
Context
StackExchange Computer Science Q#47546, answer score: 3
Revisions (0)
No revisions yet.