Re: [FWP] Fun with complexity classes

[Robin Houston <robin@kitsite.com>]

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.

Well, you can do arithmetic on tallies quite easily: i.e. to see
whether $x + $y == $z, just check ("1"x$x).("1"x$y) =~ /^1{$z}$/;
(Or see Abigail's delightful regex primality tester)

but the length of a tally is exponential in the number of bits, and
so you're unlikely to be able to get a polynomial reduction using
that method.

hence the vast majority of the code below is dealing with the details
of adding two n-bit numbers using regex matching. It's not very well
commented, but I'm happy to answer questions; or consider it a puzzle
:-)

 .robin.

#!/usr/bin/perl -w

##
# A reduction of the subset-sum problem to regex matching with backrefs.
#
# robin@kitsite.com, June 2001 
##

use strict;

sub subset_sum {
    my ($total_in, @nums_in) = @_;
    
    # Convert the total into the reversed binary notation we'll be using:
    my $total = reverse sprintf("%b", $total_in);
    my $nbits = length $total;
    
    # Prepare the "full adder" string:
    my $adder = ",000 00,001 01,010 01,011 10,100 01,101 10,110 10,111 11";
    
    my ($str, $re) = ("", "");
    my @subtotal = (0)x$nbits;
    
    my $c = 0;
    for my $num_in (@nums_in) {
	my @N = split//, reverse sprintf("%0${nbits}b", $num_in);  # Reversed bits of number into @N
	my ($yes, $no) = ("", "");
	
        my $carry = 0;
	for (my $i = 0; $i < $nbits; ++$i) {
	    $yes .= "[^;]*,$subtotal[$i]$carry$N[$i] ([01])([01])[^;]*;01;";
	    $no  .= "[^;]*;0?($subtotal[$i])1?;";
	    
	    $subtotal[$i] = "(?:\\".($c + $i*2 + 2) . "|\\".($c + 2*$nbits + $i + 1) .")";
	    $carry        = "(?:\\".($c + $i*2 + 1) . ")";
	    
	    $str .= "$adder;01;"
	}
	
	# Make sure that the carry bit is zero at the end (i.e that we haven't overflowed)
	$re  .= "(?:$yes$carry;|${no}0;)";
	$str .= "0;";
	
	$c += 3 * $nbits;
    }
    # See if the total matches
    $re  .= (join "", @subtotal);
    $str .= $total;

    print "String: $str\nRegex: $re\n";
    return ($str =~ /^$re$/);
}

print (subset_sum(5, 2,3,4) ? "Yes\n" : "No\n");

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe