←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 3 comments | 17 Apr 25 07:34 UTC | HN request time: 0.712s | source
Show context
ykonstant ◴[17 Apr 25 09:21 UTC] No.43714569[source]▶
I am confused about the precise statement of the problem that is claimed to be provably NP-hard, decidable and not in NP. Any clarification?
replies(2): >>43714692 #>>43714727 #
1. ngkabra ◴[17 Apr 25 09:47 UTC] No.43714727[source]▶
The article talks about a 2-dimensional grid which starts at (0,0) (bottom right) and extends infinitely to the right and the top, so all (x,y) for non-negative integers x,y exist. But x or y negative does not exist. Given a list of possible jumps e.g. (+1,+10) or (-20,+13), and a target destination, e.g. (700,1). Does there exist a series of valid jumps that takes you from (0,0) to (700,1) without ever going off grid (i.e. into negative territory)?

This problem might or might not be NP-Harder. However, now extend the problem to higher dimensional grids. At some number of dimensions, the problem becomes definitely NP-Harder (i.e. NP-hard, decidable, but not in NP)

replies(1): >>43716147 #
2. ykonstant ◴[17 Apr 25 12:57 UTC] No.43716147[source]▶
Which number of dimensions, though? Is there an effective bound? Otherwise it is hard to suggest the problem as an example.
replies(1): >>43723006 #
3. thaumasiotes ◴[17 Apr 25 22:41 UTC] No.43723006[source]▶
The number of dimensions is one of the variables in the problem.