←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 4 comments | 17 Apr 25 07:34 UTC | HN request time: 0.226s | 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 #
hwayne ◴[17 Apr 25 14:10 UTC] No.43717130[source]▶
To be in NP, witness must be verifiable in polynomial time with respect to the size of the original input. In this problem (VAS Reachability), the solution can be `2^2^2^...^K` steps long. Even if that's linear with respect to the witness, it's not polynomial with respect to the set of moves + goal.
replies(1): >>43719822 #
andrewla ◴[17 Apr 25 17:27 UTC] No.43719822[source]▶
Hmm.. I'd love to see a more formal statement of this, because it feels unintuitive.

Notably the question "given a number as input, output as many 1's as that number" is exponential in the input size. Is this problem therefore also strictly NP-hard?

replies(4): >>43720615 #>>43720809 #>>43725660 #>>43726574 #
1. johntb86 ◴[17 Apr 25 18:40 UTC] No.43720615[source]▶
It needs to be a decision problem (or easily recast as a decision problem). "given a number as input, output as many 1's as that number" doesn't have a yes or no answer. You could try to ask a related question like "given a number as input and a list of 1s, are there as many 1s as the number?" but that has a very large input.
replies(1): >>43721383 #
2. andrewla ◴[17 Apr 25 19:51 UTC] No.43721383[source]▶
Straightforward to pose as a decision problem -- you're given a sequence of {0,1} representing a base-2 input (N), output a string of {0, 1} such that there are N 1's. You could make it "N 1s followed by N 0s" to avoid being too trivial, but even in the original formulation there are plenty of "wrong" answers for each value of N, and determining whether a witness is correct requires O(2^b) time, where b is the number of bits in N.
replies(2): >>43722470 #>>43725713 #
3. ◴[17 Apr 25 21:33 UTC] No.43722470[source]▶
4. bubblyworld ◴[18 Apr 25 07:01 UTC] No.43725713[source]▶
That's not a decision problem either. You need to cast it in the form of determining membership in some set of strings (the "language"). In this case the natural choice of language is the set of all strings of the form "{encoding of n}{1111....1 n times}", which is decidable in O(log(n)+n) steps, i.e. linear time.