  In this paper we show that the following problem is NP-complete: Given an
alphabet $\Sigma$ and two strings over $\Sigma$, the question is whether there
exists a permutation of $\Sigma$ which is a subsequence of both of the given
strings.
