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.
--
Jeff "japhy" Pinyan [EMAIL PROTECTED] http://www.pobox.com/~japhy/
I am Marillion, the wielder of Ringril, known as Hesinaur, the Winter-Sun.
Are you a Monk? http://www.perlmonks.com/ http://forums.perlguru.com/
Perl Programmer at RiskMetrics Group, Inc. http://www.riskmetrics.com/
Acacia Fraternity, Rensselaer Chapter. Brother #734
** Manning Publications, Co, is publishing my Perl Regex book **
