1
$\begingroup$

The standard technique to show NP-completeness of $L$ seems to be to show that $L$ is in NP, and then to show that some NP-complete language can be reduced to it. What if one tried to show it the other way, i.e., if L $\leq $ 3SAT?

Wouldn't that be one one step way of showing that the language $L$ is in NP-complete?

$\endgroup$
2
$\begingroup$

Here is a counterexample to your proof method. The empty language reduces to 3SAT, yet it isn't NP-hard.

If you reduce $L$ to 3SAT, then you can conclude that $L$ is in NP, that's it.

$\endgroup$
2
  • $\begingroup$ Since 3SAT can be reduced to the Halting problem, wouldn't the empty language too be reducible to it? And by extension be in NP-Hard. $\endgroup$ Oct 11 at 11:44
  • 1
    $\begingroup$ The empty language reduces to any language except for the complete language. $\endgroup$ Oct 11 at 11:44

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.