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):
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)