0
$\begingroup$

If L is NP-complete then how can I prove that $L_1$:

$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$}

is also NP- complete.

My thoughts: A reduction from (for example) SAT to L can be converted to a reduction to { $0x | x \in L$} by adding a 0 to the output.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

There is a somewhat trivial reduction from $L$ to $L_1$…

Consider $x\in \Sigma^*$. Then $x\in L \Leftrightarrow 0x\in L_1$. Clearly this reduction is polynomial.

I am sure that you can prove that $L_1\in \mathsf{NP}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the reduction to $L_1$ is the same as to { $0x | x \in L$}? $\endgroup$
    – Hjm
    Commented Jan 9, 2023 at 9:41
  • $\begingroup$ Well, yes, it would be the same. $\endgroup$
    – Nathaniel
    Commented Jan 9, 2023 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.