On Fri, Jul 06, 2001 at 12:02:15AM -0400, Jeff 'japhy' Pinyan wrote:
> >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$/;
> }
Abigail has already explained what's wrong with this. (I also mentioned
that using tally arithmetic won't work in my original message, but I
obviously didn't explain it very clearly).
Anyway, there's another interesting way to look at it.
1. It is "well known" that matching simple regexes (without backrefs)
can be done in time O( length($string) * length($regex) ). [*]
That's definitely polynomial time.
2. The regex constructed above will never have backrefs.
3. So, supposing the reduction above to be correct, you've succeeded
in reducing an NP-complete problem to a P problem, in polynomial
time.
4. Therefore, all in polynomial time, you can:
- turn an instance of subset-sum into a regex-match
- decide whether the regex matches or not
...which constitutes a polynomial-time algorithm for the subset-sum
problem.
So you've proved that P=NP, and you become rich and famous!
.robin.
[*] See for example http://www-igm.univ-mlv.fr/~mac/REC/DOC/B4.ps
(section 4).
--
Flee to me, remote elf!
