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.

DeleteThanks Lance. What a pity!!! Certainly the following proof would be revelant,

Deletehttp://hal.archives-ouvertes.fr/hal-01070568

if my suspicious were right. Unfortunately, I'm not. However, I would like to share it, maybe you or somebody else see some benefits on this proof. Here is the abtract,

<<$ONE-IN-THREE \ 3SAT$ is the problem of deciding whether a given boolean formula $\phi$ in $3CNF$ has a truth assignment such that each clause in $\phi$ has exactly one true literal. This problem is $NP-complete$. We define a similar language: $ZERO-ONE-IN-THREE \ 3SAT$ is the problem of deciding whether a given boolean formula $\phi$ in $3CNF$ has a truth assignment such that each clause in $\phi$ has at most one true literal. Indeed, $ONE-IN-THREE \ 3SAT \subseteq ZERO-ONE-IN-THREE \ 3SAT$. In this work, we prove $ZERO-ONE-IN-THREE \ 3SAT \in P$.>>

I hope it might be interesting even though is a very trivial proof.

Professor in a book of Computational Complexity there is a question that states: If L1 is NP-complete and L2 is co-NP-complete, then the intersection of L1 with L2 is DP-complete (True or false?). I suspect the answer is true. However, I'm not quite sure. Could you help me to clarify this doubt, please? Thanks in advance.

ReplyDeleteI won't answer questions in textbooks. But here's a hint: Intersections of sets from complexity classes can do funny things.

Delete