Reconhecendo seqüências com todas as permutações de como subsequências

25

Para qualquer , digo que uma sequência de números inteiros em é completa se, para cada permutação de , escrita como uma sequência de números inteiros distintos , a sequência é uma subsequência de , ou seja, existede modo que para todos os .s { 1 , , n } n p { 1 , , n } p 1 , , p n p s 1 i 1 < i 2 < < i n| s | s i j = p j 1 j nn>0s{1,,n}np{1,,n}p1,,pnps1i1<i2<<in|s|sij=pj1jn

Qual é a complexidade do seguinte problema? Está em PTIME, ou coNP-hard? Observe que ele está no coNP, pois você pode adivinhar uma sequência ausente (obrigado @MarzioDeBiasi).

Entrada: um número inteiro, uma sequênciade inteiros em Saída: é-completo?s { 1 , , n }ns{1,,n}
ns n

A noção de sequência -complete é conhecida na combinatória, porque as pessoas investigaram qual é o comprimento das seqüências -complete mais curtas como uma função de (consulte, por exemplo, este tópico do overflow matemático para obter um resumo). No entanto, não consegui encontrar referências à complexidade de reconhecê-las. Observe que, em particular, podemos facilmente construir sequências completas de polinômio de comprimento em , ou seja, de comprimento , como (1, \ ldots, n) repetidas n vezes (qualquer permutação \ mathbf {p} pode ser realizada por escolhendo p_i no in nnnnn n 2 ( 1 , , n ) n p p i innn2(1,,n)nppii-ésimo bloco). Portanto, não podemos nos dar ao luxo de enumerar todas as permutações.

a3nm
fonte
10
O problema está no coNP porque uma permutação ausente p1...pn da sequência s pode ser verificada em tempo polinomial. Portanto, o problema poderia ser coNP-complete
Marzio De Biasi
@MarzioDeBiasi: certo, isso foi desleixado, editei de acordo. Obrigado!
a3nm

Respostas:

13

Acredito que o problema seja coNP-completo. Fiz o upload como uma pré-impressão do arXiv .

Przemysław Uznański
fonte
2
Analisei essa prova em detalhes e confirmo que ela me parece correta. Muito obrigado!
a3nm
2
Sua versão do arXiv está disponível: arxiv.org/abs/1506.05079
Tyson Williams