Consider any problem in NP-hard, then it has a polynomial reduction from a problem in NP in polynomial time. Though, it isn't clear by this definition whether there are decision problems in NP-hard that are not in NP.

Are there any known ones?

  • 3
    $\begingroup$ Have you checked the definition of NP and NP-hard at wikipedia? $\endgroup$ – John L. Mar 13 '19 at 14:21
  • $\begingroup$ I did read it lightly, it is indeed answered there as I see now but I missed it somehow. anyway I think It's good it's here as well, as I think it's quite an important fact and it isn't here and isn't very emphasized in Wikipedia $\endgroup$ – Oren Mar 13 '19 at 19:47
  • $\begingroup$ I'm sure we have several duplicates of this. Anyone got one handy? $\endgroup$ – Raphael Mar 13 '19 at 19:58

The nondeterministic time hierarchy theorem shows that, e.g., $\mathrm{NP}\subsetneq\mathrm{NEXP}$, so any $\mathrm{NEXP}$-complete problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$. For a more extreme example, the halting problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$.


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.