# Manipulating Intersection of oracles

Suppose for different classes $A,B,C$ we have that $A\subseteq P^B$ and $A\subseteq P^C$.

1. We have $A\subseteq P^{B}\cap P^{C}$. Does it also mean $A\subseteq P^{B\cap C}$?

2. Supposing $A\subseteq P^{B\cap C}$ also holds does it also give $A\subseteq {B\cap C}$?

3. If $P^B=B$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?

4. If $B\subseteq P^{B\cap C}$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?

Do we know anything else about intersection of oracles?

• One question per post, please. Also, "Do we know anything else about X?" is too broad for this site. – D.W. Dec 26 '17 at 18:52

## 1 Answer

The answer to all of those questions is no, and not for some especially deep reason, as most of these can be ruled out by forcing the intersection to be simple enough.

Suppose $B$ contains all languages with only even length words, and $C$ contains all languages with odd length words. Clearly $B\cap C =\emptyset$, so $\mathsf{P^{B\cap C}=P}$, but $P^B, P^C$ both contain undecidable problems. This example rules out $1,2$.

To rule out $3$ you can set $\mathsf{B=EXP}$ and $C=\emptyset$. Choosing $B=\emptyset$ rules out $4$. Not allowing the empty set won't change much, as we can always do the same tricks with finite languages (or simple infinite langauges), so it is probably not possible to claim anything interesting in the general case.

• Sorry my consideration was within PSPACE (should have mentioned this). – Bread Winner Dec 26 '17 at 9:39
• Indeed you should have. Well, $1,3$ (the second part of 3) are now true if $P=PSPACE$, so you can't disprove them unconditionally, but the same examples work if you assume $P\neq PSPACE$ (just pick $B=PSPACE$ for $3$). – Ariel Dec 26 '17 at 9:49
• – Bread Winner Dec 26 '17 at 10:00
• If $A\subseteq B$ then $A=A\cap B$? Essentially I ask is following. $A$ accepts if condition 1 and rejects if condition 2 and $B$ accepts if condition 1' and rejects if condition 2'. Then $A\cap B$ accepts if condition 1 and 1' and rejects if condition 2 and 2'. This seems a bit stronger that $A$. – Bread Winner Dec 31 '17 at 10:15