1

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.

Joe Shmo
  • 977
alphabinary
  • 13

1 Answers1

1

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$.

mihaild
  • 15,368
  • Thank you for your answer. So you mean that $L$ and $T$ ar $NP-complete$ because they contain $S$ ?, and $\lambda$ is the empty string? – alphabinary Jun 08 '22 at 11:59
  • They don't contain $S$ (and containing an np-complete language doesn't say anything about complexity), but $S$ can be easily reduced to them (do you understand, how?), so they are NP-hard, and also they can be solved on non-deterministic machine if $S$ can be, so they are in NP. – mihaild Jun 08 '22 at 12:02
  • Yes, $\lambda$ is empty string (other common notation in such contexts is $\epsilon$). – mihaild Jun 08 '22 at 12:03