HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canallhardoneanotherproblemsreduced

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#53981, answer score: 3

Revisions (0)

No revisions yet.