0
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ That would be a nice homework question. $\endgroup$ – Neal Young Dec 3 at 1:09
  • $\begingroup$ If P = NP, then every NP language is NP-hard, not every non-trivial language. Or am I confused? $\endgroup$ – Sasho Nikolov Dec 3 at 14:07
  • $\begingroup$ 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. $\endgroup$ – chad Dec 3 at 14:11
  • 3
    $\begingroup$ @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. $\endgroup$ – Huck Bennett Dec 3 at 15:20
  • $\begingroup$ @chad ah ok, thanks! $\endgroup$ – Sasho Nikolov Dec 4 at 22:35