←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 2 comments | 17 Apr 25 07:34 UTC | HN request time: 0.442s | source
Show context
graycat ◴[17 Apr 25 08:08 UTC] No.43714234[source]▶
Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem".

Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b).

replies(6): >>43714273 #>>43714285 #>>43714402 #>>43714513 #>>43714742 #>>43717019 #
Sankozi ◴[17 Apr 25 08:19 UTC] No.43714285[source]▶
Yes, lots of these problems assume fantasy infinite world.

Big O notation also suffers from this - it's almost useless for real world problems.

replies(5): >>43714298 #>>43714309 #>>43714328 #>>43714554 #>>43718244 #
suddenlybananas ◴[17 Apr 25 08:23 UTC] No.43714298[source]▶
>Big O notation also suffers from this - it's almost useless for real world problems.

It's not the only way to optimize things but there's a reason no one sorts with bubble sort.

replies(2): >>43714316 #>>43716864 #
1. LegionMammal978 ◴[17 Apr 25 13:52 UTC] No.43716864[source]▶
Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms.

In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.

replies(1): >>43717276 #
2. Al-Khwarizmi ◴[17 Apr 25 14:21 UTC] No.43717276[source]▶
Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.