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?
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?
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)
Which number of dimensions, though? Is there an effective bound? Otherwise it is hard to suggest the problem as an example.
The number of dimensions is one of the variables in the problem.
Given a dimension, n; a collection of n-dimensional vectors of integers v_1,..,v_k; and a target n-dimensional vector u: Is there a sequence of vectors from the collection which sums to u, such that no partial sum(of an initial segment of the sequence) has any negative components?