Remix.run Logo
ykonstant 6 days ago

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?

ngkabra 6 days ago | parent | next [-]

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)

ykonstant 6 days ago | parent [-]

Which number of dimensions, though? Is there an effective bound? Otherwise it is hard to suggest the problem as an example.

thaumasiotes 5 days ago | parent [-]

The number of dimensions is one of the variables in the problem.

penteract 6 days ago | parent | prev [-]

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?