  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.
