6
$\begingroup$

I know that all NP-complete problems can be reduced to each other, but how about NP-hard problems? Can all NP-hard problems be reduced to one another?

$\endgroup$
7
$\begingroup$

The answer to your question is no. Take for example the $SAT$ problem and Halting problem. Both are NP- Hard but second can't be reduced to first.

$\endgroup$
2
$\begingroup$

Can all NP-hard problems be reduced to one another?: No.

But can all NP-complete be reduced to NP-hard problems?: Yes

Remember: $L \text{ is NP-hard } \wedge L \in NP \rightarrow L \text{ is NP-complete}$

And NP-hard means, all problems in NP can be reduced to one NP-hard one, but not the other way around, since not all NP-hard problems are also in NP.


(Update):

So not all NP-hard problems can be reduced to another, because they aren't all in NP. One could say basically this:

$P \subseteq NP \subseteq \text{\{decidable problems\}} \subset \text{\{decision problems\}}$

The halting problem e.g. is not decidable. But complexity classes like NP are saying how much time it takes to decide/verify a problem. Obviously the halting problems takes infinite time aka forever, so $\notin NP$. But since it is defined for all programs i.e. input, it could solve all problems in NP like SAT, so the halting problem is NP-hard. So SAT is reduce able to the halting problem. But you can't reduce the halting problem to SAT, since SAT is decidable (and also NP-complete), while the halting problem is not.

$\endgroup$
  • $\begingroup$ Looks much better. By the way, you could make the inclusion between NP and the decidable problems strict: we know that there are decidable problems that aren't in NP: for example, the nondeterministic version of the time hierarchy theorem says that NEXP-complete problems can't be in NP. $\endgroup$ – David Richerby Mar 7 '16 at 19:50
  • $\begingroup$ @DavidRicherby Good to know. Will do as soon as I at least halfway understood the two theorems (time hierachy, and the space one) :-) $\endgroup$ – Superlokkus Mar 9 '16 at 13:21

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.