5
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$

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.