# Assuming P != NP, what is the cardinality of the set of NP-Hard languages?

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.

• Hint: The class NP is clearly countable and a superset of the complement of NP-hard languages. – ttnick Dec 3 '19 at 13:28
• 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. – chad Dec 3 '19 at 13:57
• 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. – Yuval Filmus Dec 3 '19 at 14:32
• @ttnick That answer is wrong. – Arno Dec 3 '19 at 14:50
• @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. – chad Dec 3 '19 at 15:43

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}$$.