__Preprint:__

**
Sam Buss and Michael Soltys
"Unshuffling a Square is NP-Hard"
Journal of Computer and Systems Sciences, 80, 4 (2014) 766-776.
DOI: 10.1016/j.jcss.2013.11.002
**

**
Download preprint version:
PDF.
**

**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.