←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 1 comments | 17 Apr 25 07:34 UTC | HN request time: 0.237s | source
Show context
the-grump ◴[17 Apr 25 08:32 UTC] No.43714333[source]▶
Technically correct is the best kind of correct, and The Halting Problem is a fun head scratcher for a green computer scientist. I'm glad it was part of my introduction to NP hardness.

That said, you do make a great point OP, and I'll think about it every time the Halting Problem comes up.

replies(1): >>43715688 #
edanm ◴[17 Apr 25 12:16 UTC] No.43715688[source]▶
This seems weird to me. I would think the classic way to introduce these topics is to first talk about decidability, introduce the halting problem through that, then introduce complexity. That's certainly how I was introduced to this material.

I wouldn't think that you'd learn about the halting problem as only an example of something harder than NP hard.

replies(1): >>43721081 #
sfink ◴[17 Apr 25 19:26 UTC] No.43721081[source]▶
I agree. NP, NP-complete, and NP-hard are all talking about how long things take. If something is uncomputable, then how long it takes doesn't seem very relevant or interesting.

"If Jimmy earns 5 cents a day and a watermelon costs $10, how long will it take for Jimmy to earn enough money to buy the color blue?"

Maybe the connection is that it feels like the halting problem could be solved if you had an infinite amount of time?

replies(1): >>43722986 #
1. thaumasiotes ◴[17 Apr 25 22:37 UTC] No.43722986[source]▶
The halting problem obviously can be solved if you have an infinite amount of time, as long as terminating is guaranteed to take place within a finite amount of time. If it's possible to terminate after an infinite amount of time, you'll need a more infinite amount of time to check for halting.