On Fri, May 25, 2012 at 3:55 PM, Nathaniel Smith <njs@pobox.com> wrote:
On May 25, 2012 2:21 PM, "Robert Kern" <robert.kern@gmail.com> wrote:
On Thu, May 24, 2012 at 5:52 PM, Robert Kern <robert.kern@gmail.com> wrote:
(Hmm, now that I think about it, the edge cases are when the strides are 0 or negative. 0-stride axes can simply be removed, and I think we should be able to work back to a first item and flip the sign on the negative strides. The typical positive-stride solution can be found in an open source C++ global array code, IIRC. Double-hmmm...)
Except that it's still NP-complete.
Huh, is it really? I'm pretty sure checking the existence of a solution to a linear Diophantine equation is cheap, but I guess figuring out whether it falls within the "shape" bounds is less obvious...
If both positive and negative values are allowed, then there is a polynomial-time algorithm to solve the linear Diophantine equation, but bounding the possible values renders it NP-complete. When you go down to {0,1} as the only allowable values, it becomes the SUBSET-SUM problem. -- Robert Kern