Problem Detail: Given disjoint languages $X$ and $Y$, where $X$ is NP-complete and $Yin P$ , how do I prove that $Xcup Y$ is NP-complete? My idea is to prove that $(Xcup Y)in NP$ and then prove that $Xcup Y$ is NP-hard: I can prove $(Xcup 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 $Xcup 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 $Xcup 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 Yin P Rightarrow Xcup Ytext{ is NP complete}$ then $Pneq NP$. Let $L$ be some NP-complete language. $Lcupoverline{L}=Sigma^*$ is not NP-complete, thus, using (*) we obtain $overline{L}notin P$, but $Lin Piff overline{L}in P$. In fact your statement is equivalent to $Pneq NP$. You can prove the opposite direction by using the fact that if $Pneq NP$ and $L$ is NP-complete, then $overline{L}$ is not in $P$. In that case, you can reduce $X$ to $Xcup Y$ by checking if the input is in $Y$, and output some constant word outside of $Xcup Y$ if it is. This can be done since we know now that $Ysubsetneq overline{X}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/65538 Ask a Question Download Related Notes/Documents
