Can someone give me an example of an undecidable problem that is not NP-hard?
I'm unable to understand the difference between the two.
Thanks very much!
Asked
Active
Viewed 300 times
-3
-
[Did you read this?](https://stackoverflow.com/questions/10494133/relationship-between-np-hard-and-undecidable-problems) – sascha Jul 01 '17 at 12:52
-
I'm voting to close this question as off-topic because it's not related to programming. – sascha Jul 01 '17 at 12:53
-
Could you help me out with this question instead? – user3740951 Jul 01 '17 at 13:30
1 Answers
2
An NP-hard problem is one such that every problem in NP can be reduced to it. In fact, it is "at least as hard as" the problems in NP class. For example, TSP (Traveling Sales Person) is NP-hard. However, undecidable is a problem for which there is no algorithm that always decide correctly. For example, the question of whether a program halts at some point or not is undecidable. In fact, you may not have an algorithm that can answer this question correctly for all programs in the world. (This can be proved)
So, in brief, an undecidable problem is logically hard; no matter how strong your computers or algorithms are, they cannot be solved. But, NP-hard problems have algorithms to be solved with but those algorithms are not polynomial in time.
A. Mashreghi
- 1,729
- 2
- 20
- 33