Rozpoznawanie sekwencji ze wszystkimi permutacjami

Dla każdego , to znaczy, że sekwencja liczb całkowitych jest -Complete , jeżeli dla każdej permutacji o , zapisane jako sekwencja odrębnych par liczb całkowitych p 1 , … , p n , sekwencja p jest podsekwencją s , tzn. istnieje 1 ≤ i 1 < i 2 < ⋯ < i n ≤ | s $n > 0${ 1 , … , n } n p { 1 , … , n $s$$\{1, \ldots, n\}$$n$$\mathbf{p}$$\{1, \ldots, n\}$$p_1, \ldots, p_n$$\mathbf{p}$$s$$1 \leq i_1 < i_2 < \cdots < i_n \leq |s|$tak, że dla wszystkich 1 ≤ j ≤ n .$s_{i_j} = p_j$$1 \leq j \leq n$

Jaka jest złożoność następującego problemu? Czy to w PTIME, czy w trybie coNP? Zauważ, że jest w CoNP, ponieważ możesz odgadnąć brakującą sekwencję (dzięki @MarzioDeBiasi).

Wejście: liczba całkowita , sekwencję s liczb całkowitych { 1 , ... , n } Wyjście: jest e n -Complete?$n$$s$$\{1, \ldots, n\}$
$s$ $n$

Pojęcie kompletnej sekwencji jest znane w kombinatoryce, ponieważ ludzie badali, jaka jest długość najkrótszych n- pełnych sekwencji w funkcji n (patrz np. Ten wątek przepływu matematyki dla podsumowania). Nie udało mi się jednak znaleźć odniesień do złożoności ich rozpoznania. Zauważ, że w szczególności możemy łatwo zbudować n- kompletne sekwencje wielomianu długości w n , mianowicie o długości n 2 , ponieważ ( 1 , … , n ) powtarzane n razy (dowolną permutację p można zrealizować wybierając$n$$n$$n$$n$$n$$n^2$$(1, \ldots, n)$$n$$\mathbf{p}$ w i-tym bloku). Dlatego ogólnie nie możemy sobie pozwolić na wyliczenie wszystkich permutacji.$p_i$$i$

Uważam, że problem jest kompletny coNP. Przesłałem go jako preprint arXiv .