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?
$\begingroup$
$\endgroup$
-
2$\begingroup$ Possible duplicate of What is the definition of P, NP, NP-complete and NP-hard? $\endgroup$ – David Richerby Mar 4 '16 at 16:17
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
-
$\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
