5
$\begingroup$

Given disjoint languages $X$ and $Y$, where $X$ is NP-complete and $Y\in P$ , how do I prove that $X\cup Y$ is NP-complete?

My idea is to prove that $(X\cup Y)\in NP$ and then prove that $X\cup Y$ is NP-hard:

I can prove $(X\cup Y)\in NP$ by saying that since both are in NP, they each have polytime verifiers. Thus we can have a polytime verifier that on any input will use these verifiers and accept if any accept, reject otherwise.

I am stuck on the part of proving NP-hardness. The idea of arbitrary languages is throwing me off; I am trying to reduce a NP-complete problem (SAT for example) to $X\cup Y$ and using the fact that $X$ has some method to reduce to it already but I am lost as for what to do with $Y$. I am thinking that given an input for SAT, I need to somehow change the input so that I can relate acceptance in $X\cup Y$ to acceptance in SAT; same for rejection.

Any guidance would be appreciated; thanks!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Let $X$ be the $k$-Clique problem and let $Y$ be the problem that takes as input a graph $G$ and an integer $k$ and just decides whether $G$ is a graph and $k$ is an integer. Observe that $X \subseteq Y$ and hence $X \cup Y = Y$. $\endgroup$ – Pål GD Nov 7 '16 at 20:03
7
$\begingroup$

If for any two disjoint languages $X,Y$, we have:

$\textbf{*} \hspace{1mm} X \text{ is NP-complete} \land Y\in P \Rightarrow X\cup Y\text{ is NP complete}$

then $P\neq NP$.

Let $L$ be some NP-complete language. $L\cup\overline{L}=\Sigma^*$ is not NP-complete, thus, using (*) we obtain $\overline{L}\notin P$, but $L\in P\iff \overline{L}\in P$.

In fact your statement is equivalent to $P\neq NP$. You can prove the opposite direction by using the fact that if $P\neq NP$ and $L$ is NP-complete, then $\overline{L}$ is not in $P$. In that case, you can reduce $X$ to $X\cup Y$ by checking if the input is in $Y$, and output some constant word outside of $X\cup Y$ if it is. This can be done since we know now that $Y\subsetneq \overline{X}$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Which statement are you referring to in your first sentence? If $L$ is NP-complete then $\overline{L}\notin\mathbf{P}$ unless $\mathbf{P}=\mathbf{NP}$, so $L\cup\overline{L}$ is not the union of an NP-complete language and a language in P. $\endgroup$ – David Richerby Nov 4 '16 at 10:42
  • $\begingroup$ I edited for clarity $\endgroup$ – Ariel Nov 4 '16 at 12:40
  • 2
    $\begingroup$ Perhaps the following proof is clearer: if $P=NP$, then let $X$ be any $NP$-complete language and $Y=\bar{X}$ is thus in $P$. Therefore (if the statement is true) $X\cup Y = \Sigma^*$ is $NP$-complete but this is a contradiction. Therefore $P\not = NP$. $\endgroup$ – Tom van der Zanden Nov 4 '16 at 12:47
2
$\begingroup$

Here are some thought which might be helpful.

1) NP-hardness

Take a language $L$ in $NP$. There is a many-one reduction $f$ from $L$ to $X$ because $X$ is NP-Complete. So, for yes-instance you have no problem, because for $l \in L$ you have $f(l) \in X$ so $f(l) \in X \cup Y$. For the no-instance it's not that trivial because you might have for $l \notin L$ $f(l) \in Y$. To fix this case, you use the fact that $Y \in P$ and thus it is easy to tell if $f(l) \in Y$. You can confidently reject if this is the case because $X$ and $Y$ are disjoint. In the summary, your new many-one reduction becomes $$f^*(l) = \begin{cases}l_0 \text{ if } f(l) \in Y \\ f(l) \text{ o.w. } \end{cases}$$ where $l_0 \notin X \cup Y$. Verify that this will work.

2) Belonging to NP

Your idea was pretty good. It can be done several ways here, the easy one is to use the non-deterministic machine which firstly checks for belonging to $Y$, if yes - accept, if no - run the n-d machine for $X$ which exists because $X \in NP$.

Hope this helps.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Your proof holds only when there exists $l_0\notin X\cup Y$, so you assume $Y\subsetneq \overline{X}$. $\endgroup$ – Ariel Nov 4 '16 at 9:51
  • $\begingroup$ If $X$ and $Y$ are disjoin then $X \cap Y = 0$ and $Y \subset X^c$. Existence of $l_0$ is safe to assume, if no such $l_0$ then... (explore this case to have P=NP). $\endgroup$ – Eugene Nov 4 '16 at 16:23
0
$\begingroup$

$Y$ is finite, hence $Y=(X\cup Y)\setminus X$ is finite. So $Y$ is in $P$ and has a poly-time decider $D_y$.

Let's build the polynomial function $f$ from $x$ to $X\cup Y$ on input $x$:

  1. if $D_y$ accepts $x$, return $l_0$ (where $l_0 \notin X\cup Y$)
  2. else, return $x$

This is of course UNDER the assumption that $X\cup Y$ isn't trivial.

|cite|improve this answer
$\endgroup$

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.