Re: NP-complete sometimes isn't

The relevant detail in this case is that we are dealing with an array of small integers.

Are we? Do you know that? Just because the examples in the OP were all small integers, does it mean we can assume that it's always the case?

Your solution is very nice, and if it is applicable it's certainly one of the best solutions and I like it. Still you should verify your assumptions before making them (or was it actually mentioned in the original thread, and I missed it?)

Comment on Re: NP-complete sometimes isn't

Replies are listed 'Best First'.
Re^2: NP-complete sometimes isn't by tilly (Archbishop) on Sep 02, 2008 at 08:06 UTC
Well to some extent there is a guarantee on that. If they're small enough to be represented as integers in raw Perl, then they're limited in size and my solution is faster than the NP-complete one beyond some (generally not very large) number of numbers. Of course that guarantee is not particularly useful, because the program won't necessarily run on a real machine without running out of RAM. At which point I point out my weasel words, "almost certainly not NP-complete" and say that my "almost certainly" was based on my strong suspicion that most concrete programming problems which would result in this kind of question coming up involve small integers. With the critical question being how small.	[reply]

Replies are listed 'Best First'.

Re^2: NP-complete sometimes isn't
by tilly (Archbishop) on Sep 02, 2008 at 08:06 UTC

Of course that guarantee is not particularly useful, because the program won't necessarily run on a real machine without running out of RAM.

At which point I point out my weasel words, "almost certainly not NP-complete" and say that my "almost certainly" was based on my strong suspicion that most concrete programming problems which would result in this kind of question coming up involve small integers. With the critical question being how small.

[reply]