All Permutations Supersequence is coNP-complete

Przemysław Uznański

We prove that deciding whether a given input word contains as subsequence every possible permutation of integers $\{1,2,\dots ,n\}$ is coNP-complete. The coNP-completeness holds ev…