Is it possible to have two $NP$- complete languages whose union is $\{ 0, 1\}^*$?

94 Views Asked by At

I've been studying complexity theory, and it proves to be very difficult to understand for an undergrad student as myself. I have the following question:

Is it possible two have two NP-complete languages $L, T$ such that $L \cup T = \{0, 1\}^*$? I would appreciate a lot if you could provide such languages.

1

There are 1 best solutions below

3
On BEST ANSWER

The example from the question linked in comments is almost answer to your question.

Let $S$ be any NP-complete language in alphabet $\{0, 1\}$. Let $L = \{\lambda\} \cup 1S \cup 0\{0, 1\}^*$ (either empty word, or $1$ and then word from $S$, or $0$ and then any string) and $T = 0S \cup 1\{0, 1\}^*$. Then $L \cup T = \{\lambda\} \cup 0\{0,1\}^* \cup 1\{0, 1\}^* \cup 0S \cup 1S$ - the first three terms already give $\{0, 1\}^*$.

To prove that $L$ is NP-complete ($T$ is simlar) let's reduce $S$ to $L$. The reduction is quite simple: $x \to 1x$: by definition of $L$, $x \in S$ iff $1x \in L$.