[Solved]: Can all NP-hard problems be reduced to one another?

Problem Detail: 

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?

Asked By : user3590783

Answered By : sashas

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53981

3.2K people like this

 Download Related Notes/Documents