# NP-Complete is not closed under kleene star

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^*$$.
• 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. – pepito grillo May 1 '19 at 13:36
• 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 – David Richerby May 1 '19 at 13:37