New answers tagged


Yes there a concept of Pumping Lemma which is a negativity test.


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.


Subsets of recursive languages aren't always recursive or recursively enumerable. The simplest example is the language of all strings: it is clearly recursive (even regular), and all languages are its subsets including those not in $RE$. To solve this question, consider this: how many subsets does an infinite language $L$ have? What does that imply regarding ...

Top 50 recent answers are included