In fact, no complexity class can be the nontrivial union of two other classes. To formalize and prove this statement we need some definitions.

Let A and B be subsets of {0,1}^{*}. We define the join,
A⊕B, as the union of {0x | x is in A} and {1y | y is in B}. Given
a set C we define the 0-projection of C as {x | 0x is in C} and the
1-projection of C as {y | 1y is in C}. Note that the 0-projection of
A⊕B is just A and the 1-projection is just B.

Essentially every complexity class is closed under joins and projections. For example if A and B are in NP then A⊕B is also in NP. The fact that no complexity class is the nontrivial union of other classes follows from the following Lemma.

**Lemma**: Let **E**, **F** and **G** be classes of
languages that are closed under joins and projections and **G** =
**E**∪**F**. Then either **G** = **E** or **G** =
**F**.

**Proof**: Suppose the lemma is false. Let A be a set in
**G**-**E** and B be a set in
**G**-**F**. Let C = A⊕B. We have that C is in **G**
since **G** is closed under joins. Thus C is in either **E** or
**F**. Suppose C is in **E**. Since **E** is closed under
projections, we have A is in **E** a contradiction. If C is in
**F** then B is in **F** also a contradiction.

Hi!! Lance, I suspect that every subset of a language in NP is in NP too. How right or wrong am I? Indeed, I'm wondering if each subset of a language in P is also in P, because maybe it might depend whether P is equal to NP or not. I would appreciate your answer very much, please.

ReplyDeleteSigma^* (the set of all strings) is in both P and NP and every set (including the halting problem) is a subset of Sigma^*. So it is not the case that every subset of a language in P or NP is in P or NP.

Delete