All "nice" Complexity classes are closed under finite union and intersection. (By "nice" I mean ones with complete problems or leaf languages, e.g. P, NP, PSPACE, etc.)

But such classes are not closed under infinite union and intersection. Why?


1 Answer 1


Consider the "singleton" languages: $L=\{w\}$ for some fixed word $w$. (e.g., the language $L=\{00010100\}$ would be a singleton language) Most "nice" complexity classes include the singleton languages.

Every language can be written as an infinite union of singleton languages. So, if all singleton languages are in the class, and if the class is closed under infinite union, then all languages are in the class.

Thus, if there is any language at all that isn't in such a complexity class yet it does contain all the singleton languages, then the class cannot be closed under infinite union.

  • 1
    $\begingroup$ Thanks! nice. What about inf intersection? that seems more difficult... $\endgroup$
    – DeeDee
    Apr 28, 2020 at 21:26
  • $\begingroup$ @RingRing, if it's closed under complement, then that follows by a similar argument... $\endgroup$
    – D.W.
    Apr 28, 2020 at 22:59
  • $\begingroup$ For intersection, even if it's not closed under complement like NP, it should contain all cofinite languages and thus closure under intersection means it contains all languages. $\endgroup$ Apr 29, 2020 at 4:33

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.