Re:The Halting Problem is a terrible example of NP-Harder
by ykonstant on Thursday April 17, 2025 @08:57AM
(#43716147)
Which number of dimensions, though? Is there an effective bound? Otherwise it is hard to suggest the problem as an example.
Re:The Halting Problem is a terrible example of NP-Harder
by thaumasiotes on Thursday April 17, 2025 @06:41PM
(#43723006)
The number of dimensions is one of the variables in the problem.
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)