This result was (as far as I know) first published in 1990 by Aho. [1] In 2001 I posted online a reduction from SUBSET-SUM to regular expression matching with

This result was (as far as I know) first published in 1990 by Aho. [1] In 2001 I posted online a reduction from SUBSET-SUM to regular expression matching with back-references (which I worked out on paper while on holiday, in the days before the internet was readily accessible from Greek islands). [2] 1. A. Aho. Algorithms for finding patterns in strings. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 5, pages 255–300. Elsevier, Amsterdam, 1990. 2. http://bumppo.net/lists/fun-with-perl/2001/06/msg00008.html http://bumppo.net/lists/fun-with-perl/2001/06/msg00008.html