HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
assumingthecardinalitywhatlanguageshardset

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#118002, answer score: 8

Revisions (0)

No revisions yet.