←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: 0s | source
Show context
andrewla ◴[17 Apr 25 13:00 UTC] No.43716179[source]▶
The example given doesn't seem right to me.

> There is one problem, though, that I find easily explainable. Place a token at the bottom left corner of a grid that extends infinitely up and right, call that point (0, 0). You're given list of valid displacement moves for the token, like (+1, +0), (-20, +13), (-5, -6), etc, and a target point like (700, 1). You may make any sequence of moves in any order, as long as no move ever puts the token off the grid. Does any sequence of moves bring you to the target?

If someone gives you such a sequence, it seems trivial to verify it in linear time. Even for arbitrary dimensions, and such witness can be verified in linear time.

replies(4): >>43716238 #>>43716279 #>>43716408 #>>43717130 #
trixthethird ◴[17 Apr 25 13:19 UTC] No.43716408[source]▶
Linear time in the length of the sequence, yes. But is the sequence length linear in dimension size, or number of moves given? Thats what is interesting.
replies(2): >>43716470 #>>43716556 #
bjornsing ◴[17 Apr 25 13:25 UTC] No.43716470[source]▶
It doesn’t need to be linear though. Polynomial is enough.

But I guess it can be proven that the shortest possible sequence grows faster than polynomial.

replies(2): >>43716512 #>>43720853 #
1. hwayne ◴[17 Apr 25 19:04 UTC] No.43720853[source]▶
Proving it's nonpolynomial is pretty easy: just make the goal vector `(10, 10, 10)` and the displacement vectors `{(1, 0, 0), (-10, 1, 0), (-10, -10, 1)}`. It takes ~1000 steps to reach the goal, and if we add one more dimension we need 10x more steps.

So it grows, at least, exponentially. Back in 1970ish someone found a problem that's at least double-exponential, proving it was 2-EXPTIME-hard. It was conjectured to be 2-EXPTIME-complete for the longest time, but turned out to be significantly harder.