Tag Info

2

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.

2

The classical reference on NP-completeness is Garey and Johnson's Computers and Intractability, which contains a compendium of over 300 NP-complete problems, with links to papers proving their NP-hardness. The only downside is that the book is quite old, dating from 1979.

1

No. However, its true that $L_2$ is at least as hard as $L_1$. The opposite isn't true: take for example $L_2$ being the halting problem, and $L_1=\emptyset$.

Only top voted, non community-wiki answers of a minimum length are eligible