# Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct integers $p_1, \ldots, p_n$, the sequence $\mathbf{p}$ is a subsequence of $s$, i.e., there exist $1 \leq i_1 < i_2 < \cdots < i_n \leq |s|$ such that $s_{i_j} = p_j$ for all $1 \leq j \leq n$.

What is the complexity of the following problem? Is it in PTIME, or coNP-hard? Note that it is in coNP as you can guess a missing sequence (thanks @MarzioDeBiasi).

Input: an integer $n$, a sequence $s$ of integers in $\{1, \ldots, n\}$
Output: is $s$ $n$-complete?

The notion of $n$-complete sequence is known in combinatorics because people have investigated what is the length of the shortest $n$-complete sequences as a function of $n$ (see, e.g., this mathoverflow thread for a summary). However, I was unable to find references to the complexity of recognizing them. Note that in particular we can easily build $n$-complete sequences of length polynomial in $n$, namely, of length $n^2$, as $(1, \ldots, n)$ repeated $n$ times (any permutation $\mathbf{p}$ can be realized by choosing $p_i$ in the $i$-th block). Hence we cannot afford in general to enumerate all permutations.

• The problem is in coNP because a missing permutation $p_1...p_n$ from the string $s$ can be checked in polynomial time. So the problem could be coNP-complete May 21, 2015 at 20:53
• @MarzioDeBiasi: right, this was sloppy, I edited accordingly. Thanks!
– a3nm
May 22, 2015 at 6:06

I believe the problem to be coNP-complete. I have uploaded it as an arXiv preprint.

• I have looked into this proof in detail and I confirm that it looks correct to me. Thanks a lot!
– a3nm
Jun 15, 2015 at 9:26
• His arXiv version is up: arxiv.org/abs/1506.05079 Jun 17, 2015 at 2:30