[Proof Complexity] New preprint - Buss-Soltys

[Sam Buss]

Dear colleagues,

    Michael Soltys and I have a new preprint, "Unshuffling a Square is
NP-Hard", available from our web pages at
http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/ and
http://www.cas.mcmaster.ca/~soltys/#Papers. It is also available from the
arXiv at http://arxiv.org/abs/1211.7161.  This is not actually proof
complexity, but we hope you will not mind our posting here.

   Comments welcomed.

   Regards,

    Sam

Abstract: A shuffle of two strings is formed by interleaving the characters
into a new string, keeping the characters of each string in order. A string
is a square if it is a shuffle of two identical strings. There is a known
polynomial time dynamic programming algorithm to determine if a given string
z is the shuffle of two given strings x, y; however, it has been an open
question whether there is a polynomial time algorithm to determine if a
given string z is a square. We resolve this by proving that this problem is
NP-complete via a many-one reduction from 3-Partition.
     
(This solves a problem from the TCS stack exchange.)