1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Sorry my consideration was within PSPACE (should have mentioned this). $\endgroup$
    – Turbo
    Commented Dec 26, 2017 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
    Commented Dec 26, 2017 at 9:49
  • $\begingroup$ posted cs.stackexchange.com/questions/85936/… and cs.stackexchange.com/questions/85937/…. $\endgroup$
    – Turbo
    Commented Dec 26, 2017 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$
    – Turbo
    Commented Dec 31, 2017 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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