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

Clearly if P = NP, then every non-trivial language is NP-Hard, so there are uncountably many NP-Hard languages. However, assuming P != NP is NP-Hard known to be uncountable? My guess would be yes, but I don't know how to prove it.

• That would be a nice homework question. – Neal Young Dec 3 at 1:09
• If P = NP, then every NP language is NP-hard, not every non-trivial language. Or am I confused? – Sasho Nikolov Dec 3 at 14:07
• Every language is. Proof sketch: SAT <=p L for all non-trivial L. Since L is non-trivial, there exists a string x in L and a string x' not in L (it doesn't matter if you can compute these strings or not, just that they exist). Construct a reduction function that solves SAT in polytime and outputs x If it is satisfiable and x' o.w. – chad Dec 3 at 14:11
• @SashoNikolov: $\emptyset$ and $\Sigma^*$ are not NP-hard for the annoying reason that mapping reductions must preserve YES and NO instances, and $\emptyset$ has no YES instances and $\Sigma^*$ has no NO instances. – Huck Bennett Dec 3 at 15:20
• @chad ah ok, thanks! – Sasho Nikolov Dec 4 at 22:35