On Fri, Jul 06, 2001 at 12:02:15AM -0400, Jeff 'japhy' Pinyan wrote:
> On Jun 22, Robin Houston said:
>
> >On Mon, May 28, 2001 at 07:50:16PM -0500, Greg Bacon wrote:
> >> Can anyone write a polynomial-time reduction from SUBSET-SUM to a Perl
> >> regular expression match. Obviously there must be one (SUBSET-SUM ->
> >> 3-CNF-SAT -> regex), but is it possible to avoid the chicanery?
> >
> >Yes, I think so. It's substantially more complicated than the
> >previously-published reductions. That's because it's an arithmetic
> >problem, and doing arithmetic in regular expressions is tricky.
>
> sub subset_sum_REx {
> my $targ = shift;
> my $re = join '', map "(" . "." x $_ . ")?", @_;
> return map defined($_) ? length : (), (1 x $targ) =~ /^$re$/;
> }
>
> That's about it.
Nope. That's not polynomial, that's exponential. The amount of memory
you are using is exponential in the size of the input (that is, the
number of bits you need to represent the input).
That's why Dominus rejected Greg's first solution, IIRC.
Abigail
