2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I edited the question to improve it. $\endgroup$ – 6005 Apr 29 at 4:32
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks! nice. What about inf intersection? that seems more difficult... $\endgroup$ – DeeDee Apr 28 at 21:26
  • $\begingroup$ @RingRing, if it's closed under complement, then that follows by a similar argument... $\endgroup$ – D.W. Apr 28 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$ – 6005 Apr 29 at 4:33

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.