[FWP] Fun with complexity classes

[Greg Bacon <gbacon@fly.hiwaay.net>]

Abigail wrote a reduction[*] from 3-CNF-SAT to a Perl regular expression
match.  For the uninitiated, this confirms that matching Perl regular
expressions is a "hard" problem.

[*] <URL:http://perl.plover.com/NPC/NPC-3SAT.html>

I wrote a reduction from CLIQUE to a Perl regular expression match, and
you can read it at <URL:http://home.hiwaay.net/~gbacon/perl/clique.html>.
I believe the reduction is correct, but I welcome all comments.

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?

Greg

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