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.
