Unshuffling a square is NP-hard

作者：

Highlights：

• The problem of recognizing a square shuffle is NP-complete.

• It remains complete over finite alphabets of size 7.

• The proof is based on a many-one reduction from 3-Partition.

摘要

•The problem of recognizing a square shuffle is NP-complete.•It remains complete over finite alphabets of size 7.•The proof is based on a many-one reduction from 3-Partition.

论文关键词：Square shuffle,NP-completeness

论文评审过程：Received 15 March 2013, Revised 7 October 2013, Accepted 22 November 2013, Available online 4 December 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.11.002