# Are there decision problems outside of NP?

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?

• Have you checked the definition of NP and NP-hard at wikipedia? – John L. Mar 13 '19 at 14:21
• 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 – Oren Mar 13 '19 at 19:47
• I'm sure we have several duplicates of this. Anyone got one handy? – 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}$$.