Re:The Halting Problem is a terrible example of NP-Harder
by suzumer on Thursday April 17, 2025 @02:42PM
(#43720641)
Because a language being NP-hard implies it is at least as hard as the hardest NP problems. For any language that is NP-hard, if one had a turing machine that decided the language, one could construct a polynomial time transformation of any language in NP to the NP-hard language to decide it using the NP-hard turing machine.
[ Parent
| on HN ]
There are no comments on this comment yet.