5

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.

chad
  • 153
  • 2
  • 3
    Hint: The class NP is clearly countable and a superset of the complement of NP-hard languages. – ttnick Dec 03 '19 at 13:28
  • 3
    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 03 '19 at 13:57
  • According to this answer, your statement that there are languages outside of NP $\cup$ NP-hard w.r.t. to Karp-reductions is not true. (For me this reads like you were thinking about Ladner's Theorem, i.e. there exist languages outside of P $\cup$ NP-hard assuming P $\neq$ NP). Or are we talking about two different things? – ttnick Dec 03 '19 at 14:12
  • 1
    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 03 '19 at 14:32
  • 2
    @ttnick That answer is wrong. – Arno Dec 03 '19 at 14:50
  • @ttnick NP-hard means at least as hard as an NP-complete problem - there's no requirement that NP-hard problems be in NP. – Noah Schweber Dec 03 '19 at 15:03
  • 1
    Possible duplicate of https://cs.stackexchange.com/questions/7665/does-mathsfp-ne-mathsfnp-imply-that-mathsfnp-mathsfp, in particular see the accepted answer: P and NP are both (unconditionally) countable (by accepted I mean the top answer with 60+ upvotes) – integrator Dec 03 '19 at 15:04
  • @NoahSchweber That is not what I stated. NP-hard is at least as hard as NP-complete, NP is at most as hard as NP-complete (regarding Karp reductions), so w.r.t. Karp reductions NP = NP-hard$^C \cup$ NP-complete. However, Karp reductions seem to be a bit too weak here?! – ttnick Dec 03 '19 at 15:28
  • 2
    @ttnick I'm not thinking of Ladner's theorem. This answer (https://math.stackexchange.com/questions/235162/if-an-unary-language-exists-in-npc-then-p-np) 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 03 '19 at 15:43
  • 1
    @chad Yes, I see. Arno cleared this up! – ttnick Dec 03 '19 at 15:45
  • 1
    @ttnick It is, to my knowledge, consistent with current knowledge that there is an $X$ which is incomparable with any NP problem (under either Karp or polytime-Turing reductions). Such an $X$ is neither in NP nor is it NP-hard, so NP is not known to be a superset of the complement of the set of NP-hard problems. – Noah Schweber Dec 03 '19 at 16:26
  • 1
    In fact, it's easy to prove that for any $X\not\in P$ there is a language $Y$ which is incomparable with $X$ with respect to polynomial-time-Turing reducibility - fixing such an $X$, any sufficiently (Cohen) generic language will have this property. So indeed for each $X\not\in P$ comeager-many languages are polynomial-time-Turing incomparable with $X$. I believe the same is true replacing "comeager" with "full measure," but at a glance that seems a bit messier. – Noah Schweber Dec 03 '19 at 16:53

1 Answers1

8

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

Arno
  • 3,065
  • 10
  • 22