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 ≤ n
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 }
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 nn n 2 ( 1 , … , n ) n p p i i-ésimo bloco). Portanto, não podemos nos dar ao luxo de enumerar todas as permutações.
Respostas:
Acredito que o problema seja coNP-completo. Fiz o upload como uma pré-impressão do arXiv .
fonte