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
