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.
--
Robert Kern
_______________________________________________
NumPy-Discussion mailing list
NumPy-Discussion@scipy.org
http://mail.scipy.org/mailman/listinfo/numpy-discussion
