[Solved]: Prove NP-completeness for union of NP-complete language and language in P

Problem Detail: 

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!

Asked By : Appleboy

Answered By : Ariel

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65538

 Ask a Question

 Download Related Notes/Documents