New answers tagged

-1

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


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.


1

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