0
$\begingroup$

It is known the fact that $NP$ class is closed on sum and intersection. But, what about another complexity classes?


Ok, I have to make my question more precise:

For example: Let $C$ be any complexity class $L_1 \in C, L_2 \in C$.

Is it possible that $$ 1) \ L_1 \oplus L_2 \not \in C, \oplus \text{ is a symmetric difference}$$ $$ 2) \ L_1 \cup L_2 \not \in C$$ $$ 3) \ L_1 \cap L_2 \not \in C$$

Why I have doubts:

From point of view algebra on sets, it is true that: $L_1 \oplus L_2 \in C$ (and similarly for 2) and 3)). But, I can imagine after $\oplus$ there is no Turing machine from $C$ recognizes $L_1 \oplus L_2$ so it is not language from class $C$ though it seems that it is (algebra on sets says it).

Please explain because it is evident that my reasoning is cheesy.

$\endgroup$
  • $\begingroup$ It depends on the complexity class... but most are closed under union and intersection. $\endgroup$ – Yuval Filmus Aug 26 '17 at 8:03
  • $\begingroup$ @YuvalFilmus, I edited my post. $\endgroup$ – Logic Aug 26 '17 at 8:27

Your Answer

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

Browse other questions tagged or ask your own question.