# Prove NP-completeness for union of NP-complete language and language in P

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!

• 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$. – Pål GD Nov 7 '16 at 20:03

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

• 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. – David Richerby Nov 4 '16 at 10:42
• I edited for clarity – Ariel Nov 4 '16 at 12:40
• 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$. – Tom van der Zanden Nov 4 '16 at 12:47

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.

• Your proof holds only when there exists $l_0\notin X\cup Y$, so you assume $Y\subsetneq \overline{X}$. – Ariel Nov 4 '16 at 9:51
• 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). – Eugene Nov 4 '16 at 16:23

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