Hacker News

points by demibabs 3 days ago | 0 comments

Oh ok, I understand what you mean.

(By the way, I think you mean NP-complete, not NP-hard. The Halting Problem is NP-hard.)

The halting problem is NP hard, technically speaking, but it's much harder than that - it's uncomputable. I don't think it's common to refer to it as NP-hard because it's confusing.

[–] isaacfrond 2 days ago

Right. To be clear: the halting problem is not in the class NP. Any problem in NP can trivially be reduced to the halting problem and so the latter is NP-hard.

[–] triMichael 3 days ago

Thanks for the correction! I updated my answer to fix that :)