[Numpy-discussion] Checking for views (was: Should arr.diagonal() return a copy or aview?)

Robert Kern robert.kern at gmail.com
Fri May 25 11:59:52 EDT 2012


On Fri, May 25, 2012 at 3:55 PM, Nathaniel Smith <njs at pobox.com> wrote:
> On May 25, 2012 2:21 PM, "Robert Kern" <robert.kern at gmail.com> wrote:
>>
>> On Thu, May 24, 2012 at 5:52 PM, Robert Kern <robert.kern at 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



More information about the NumPy-Discussion mailing list