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?

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

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.

  • $\begingroup$ Sorry my consideration was within PSPACE (should have mentioned this). $\endgroup$ – Bread Winner Dec 26 '17 at 9:39
  • $\begingroup$ 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$). $\endgroup$ – Ariel Dec 26 '17 at 9:49
  • $\begingroup$ posted cs.stackexchange.com/questions/85936/… and cs.stackexchange.com/questions/85937/…. $\endgroup$ – Bread Winner Dec 26 '17 at 10:00
  • $\begingroup$ 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$. $\endgroup$ – Bread Winner Dec 31 '17 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.