Consider $\Sigma=\{0,1\}$. Suppose that $L \subset \Sigma^*$ is $NP-$Complete. How can I prove that $L' = L \cup \{0,1\}$ is $NP-$Complete?


$L$ is $\mathrm{NP}$-complete, so, for any $X\in\mathrm{NP}$, there is a many-one reduction $f_X$ from $X$ to $L$. Just modify $f_X$ so that it's a reduction to $L'$ instead. Note that $f_X$ already does the right thing unless you have some $w$ such that $f_X(w)\in\{0,1\}$.

Note that the same technique shows that $L\cup S$ is still $\mathrm{NP}$-complete for any finite $S\subseteq \Sigma^*$.

| cite | improve this answer | |
  • $\begingroup$ If $\omega \in X$ then $f_X(\omega) \in X$. However, if $\omega \notin X$ then $f_X(\omega)$ could be $0$ or $1$. I guess that you have to assign a word that 's not in $L \cup \{0,1\}$ but you have to find that word and $f'$ have to be polynomial. $\endgroup$ – pepito grillo May 1 '19 at 13:36
  • $\begingroup$ You don't have to find that word. The language $X$ is fixed, so the reduction doesn't need to compute these words: they can be "hard-coded" into its definition. Imagine that the reduction is performed by a computer program: you might have to do a lot of work to find those strings so you can write that program, but you only have to do that once and it doesn't affect its running time $\endgroup$ – David Richerby May 1 '19 at 13:37

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.