On Fri, May 25, 2012 at 4:59 PM, Robert Kern <robert.k...@gmail.com> wrote: > On Fri, May 25, 2012 at 3:55 PM, Nathaniel Smith <n...@pobox.com> wrote: >> On May 25, 2012 2:21 PM, "Robert Kern" <robert.k...@gmail.com> wrote: >>> >>> On Thu, May 24, 2012 at 5:52 PM, Robert Kern <robert.k...@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.
Right. I suspect it's still pretty practical to solve for many of the arrays we care about (strides that are multiples of each other, etc.); many NP-hard problems are easy in the typical case, and for a lot of the cases we care about (e.g. disjoint slices of a contiguous array) solving the Diophantine equation will show that the bounds are irrelevant and collisions can never occur. Oh well, fortunately nothing depends on this :-). - N _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion