1
$\begingroup$

As the title says, my question is whether the set of $\mathsf{NP}$-hard languages is closed under set inclusion, i.e. whether for any $\mathsf{NP}$-hard language $L$, all subsets of $L$ are also $\mathsf{NP}$-hard. This question is related since $\emptyset$ is not $\mathsf{NP}$-hard as there is nothing we could map "yes"-instances to and $\emptyset \subseteq L$ for all $\mathsf{NP}$-hard $L$.

However, what about non-trivial subsets, i.e. languages $L'$ of the form $\emptyset \neq L' \subsetneq L$ for $\mathsf{NP}$-hard $L$? We know that $\emptyset \neq 2SAT \subsetneq SAT$ and while $SAT$ is $\mathsf{NP}$-hard, $2SAT$ is in $\mathsf{P}$. This suggests to me that whether the set of $\mathsf{NP}$-hard is closed under "non-trivial" inclusions depends on whether $\mathsf{P} = \mathsf{NP}$. Am I mistaken here?

In one sentence, my question is this: is the set of $\mathsf{NP}$-hard languages closed under nontrivial set inclusion (1) assuming $\mathsf{P} = \mathsf{NP}$ and (2) assuming $\mathsf{P} \neq \mathsf{NP}$?

$\endgroup$
4
$\begingroup$

Indeed, if NP=P then every nontrivial problem is NP-hard, and in particular every nontrivial subset of an NP-hard problem (thus closing it to inclusion).

$\endgroup$
  • $\begingroup$ That's what I figured, and I'm really surprised by it - it seemed "obvious" to me that regular languages should not be NP-hard. Do you know a proof that regular languages are not NP-hard assuming P $\neq$ NP? $\endgroup$ – G. Bach May 19 '14 at 15:16
  • 2
    $\begingroup$ Regular languages are in P. If a language in P is NP-hard then P=NP: given a language in NP, reduce it to your language in P to get a polytime algorithm for the former. Hence if P is different from NP then regular languages are not NP-hard. Conversely, if P=NP, then as Shaull mentions, regular languages are NP-hard. $\endgroup$ – Yuval Filmus May 19 '14 at 15:57

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.