Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences For any $n &gt; 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 &lt; i_2 &lt; \cdots &lt; 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.
I believe the problem to be coNP-complete.
I have uploaded it as an arXiv preprint.