If P=NP, then every non-trivial language is NP-Hard, so clearly there are uncountably many NP-Hard languages. However it's less clear to me what the cardinality of this set is assuming P != NP.
12
-
3$\begingroup$ Hint: The class NP is clearly countable and a superset of the complement of NP-hard languages. $\endgroup$– ttnickCommented Dec 3, 2019 at 13:28
-
3$\begingroup$ That's not true though. Assuming P != NP, there exist languages which are neither NP nor NP-Hard, uncountably many in fact. For example, if P != NP, no unary language is NP-Hard. Take any unary encoding of an undecidable language and it's neither NP nor NP-Hard. $\endgroup$– chadCommented Dec 3, 2019 at 13:57
-
1$\begingroup$ Given an NP-hard language, prefix 0 to all words on the language, and union with an arbitrary language in which all words start with 1. $\endgroup$– Yuval FilmusCommented Dec 3, 2019 at 14:32
-
2$\begingroup$ @ttnick That answer is wrong. $\endgroup$– ArnoCommented Dec 3, 2019 at 14:50
-
2$\begingroup$ @ttnick I'm not thinking of Ladner's theorem. This answer (math.stackexchange.com/questions/235162/…) gives a proof that if any unary language is NP-Complete, then P = NP. However, note that the answer doesn't actually rely at all on the language at hand being in NP, so it generalizes to NP-Hard directly. $\endgroup$– chadCommented Dec 3, 2019 at 15:43
|
Show 7 more comments
1 Answer
$\begingroup$
$\endgroup$
Any upwards-closed non-empty class $\mathfrak{L}$ of languages has the cardinality of the continuum, with very few limitations on what kind of reasonable reducibility we are looking at. The reason is if $A \in \mathfrak{L}$ and $B$ is an arbitrary language, then the language $A + B = \{0w \mid w \in A\} \cup \{1w \mid w \in B\}$ satisfies that $A \leq A + B$, hence $A + B \in \mathfrak{L}$. Since $A + B = A + C$ iff $B = C$, we see that $B \mapsto A + B$ provides an injection from the all languages into $\mathfrak{L}$.
