If there is a proof that an NP-Hard problem which is not NP-Complete can be solved in P time, it does say that the verification time is polynomial too.

Why doesn't it then mean that all NP-Hard are NP (i.e. NPC)?

But, if there is something with exponential verification i.e. outside NP and since it can be reduced to an NPC problem in polynomial time which means it is also verifiable in polynomial time (As we assumed above). Isn't it? Which might say that all NP-hard is NP-complete...

I'm unable to grasp what is NP-hard but not NPC here? What is wrong in this reasoning?

Are there any problems which are outside Recursive Enumerable Languages in NP-Hard? Is that even possible?


A language $L$ is NP-hard if you can reduce every language in NP to $L$ in polynomial time. For example, the halting problem is NP-hard: if $A$ is any language in NP, say accepted by a nondeterministic polynomial time Turing machine $T$, there there is a polynomial time reduction which accepts an input $x$ and constructs a Turing machine which simulates all computation paths of $T$ on $x$, and halts if and only if any of these paths accepts.

On the other hand, the halting problem is not in NP, since it is not computable. So the halting problem is an example of an NP-hard problem which is not in NP. You can think of NP-hard problems as being "at least as hard" as all of NP. They are allowed to be even harder.

| cite | improve this answer | |
  • $\begingroup$ What about something solvable? $\endgroup$ – Tarun Maganti Dec 6 '17 at 18:10
  • $\begingroup$ Which are solvable should definitely be in NP right? $\endgroup$ – Tarun Maganti Dec 6 '17 at 18:10
  • $\begingroup$ No. Any NEXP-complete problem is NP-hard but not in NP. $\endgroup$ – Yuval Filmus Dec 6 '17 at 18:11
  • $\begingroup$ We don't know that PSPACE is a proper superset of NP. $\endgroup$ – Yuval Filmus Dec 6 '17 at 18:13
  • $\begingroup$ I just saw what that means, can you give an easy example? $\endgroup$ – Tarun Maganti Dec 6 '17 at 18:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.