Reconocer secuencias con todas las permutaciones de

Para cualquier , digo que una secuencia s de enteros en { 1 , ... , n } es n -completa si, para cada permutación p de { 1 , ... , n } , se escribe como una secuencia de enteros distintos por pares p 1 , ... , p n , la secuencia p es una subsecuencia de s , es decir, existe 1 ≤ i 1 < i $n > 0$$s$$\{1, \ldots, n\}$$n$$\mathbf{p}$$\{1, \ldots, n\}$$p_1, \ldots, p_n$$\mathbf{p}$$s$tal que s i j = p j para todos 1 ≤ j ≤ n .$1 \leq i_1 < i_2 < \cdots < i_n \leq |s|$$s_{i_j} = p_j$$1 \leq j \leq n$

¿Cuál es la complejidad del siguiente problema? ¿Está en PTIME o coNP-hard? Tenga en cuenta que está en coNP, ya que puede adivinar una secuencia que falta (gracias @MarzioDeBiasi).

Entrada: un número entero , una secuencia s de números enteros en { 1 , ... , n } Salida: ¿ es s n -completo?$n$$s$$\{1, \ldots, n\}$
$s$ $n$

La noción de secuencia -completa se conoce en combinatoria porque las personas han investigado cuál es la longitud de las secuencias n -completas más cortas en función de n (ver, por ejemplo, este hilo de mathoverflow para un resumen). Sin embargo, no pude encontrar referencias a la complejidad de reconocerlos. Tenga en cuenta que, en particular, podemos construir fácilmente n secuencias completas de polinomio de longitud en n , es decir, de longitud n 2 , como ( 1 , ... , n ) repetidas n veces (cualquier permutación p puede realizarse eligiendo$n$$n$$n$$n$$n$$n^2$$(1, \ldots, n)$$n$$\mathbf{p}$ en el i -ésimo bloque). Por lo tanto, no podemos permitirnos en general enumerar todas las permutaciones.$p_i$$i$

Creo que el problema es completo. Lo he subido como una preimpresión de arXiv .