Verificação de uma anticadeia máxima
Na teoria da ordem, uma antichain (família / desordem Sperner) é um subconjunto de um conjunto parcialmente ordenado, com a propriedade de que dois elementos não são comparáveis entre si. Uma anticadeia máxima é a anticadeia que não está apropriadamente contida em outra anticadeia. Vamos pegar o conjunto de potência de$\{1,2,\ldots, n\}$como nosso conjunto parcialmente ordenado, aqui a ordem é dada por inclusão. Então minha pergunta é, para qualquer antichain deste conjunto parcialmente ordenado, existe algum algoritmo de tempo polinomial (com relação a$n$) para verificar se essa anticadeia é de fato "máxima"? Em outras palavras, verificar se qualquer subconjunto de$\{1,2,\ldots, n\}$está contido ou contém algum conjunto da anticadeia. Aqui, esse algoritmo deve ter um tempo de execução polinomial para QUALQUER antichain.
Atualização : Para esclarecer, tratarei aqui o tamanho de nossa antichain como o parâmetro para o algoritmo de verificação. Em outras palavras, minha pergunta é: existe um algoritmo de verificação, cujo tempo de execução é polinomial em$n$ e $m$, Onde $m$é o tamanho da anticadeia. Quando o tamanho de nosso antichain$m$ é exponencial em $n$então, tal algoritmo é trivial (apenas comparando esses elementos um por um); mas quando o antichain fornecido tem tamanho O (poly (n)), este é o meu caso de interesse. Por exemplo, quando o antichain é dado por$\{\{1\}, \ldots, \{n\}\}$, certamente não precisamos fazer a comparação de força bruta.
Respostas
Observação. Originalmente, afirmei que esta era uma solução completa, mas era falsa, como mostrado por Emil nos comentários. No entanto, este argumento prova a seguinte versão mais fraca.
Posso provar que é co-NP-completo para decidir por uma família de entrada $A$ se há um conjunto $S$ que não está relacionado a todos os conjuntos em $A$. Chamarei essas famílias de máximas. Isso mostra que qualquer algoritmo de tempo polinomial possível deve explorar que a família de entrada é uma antichain, já para entradas de tamanho linear. Minha redução é do SAT.
Dado um CNF $\Psi$ sobre $n$ variáveis, nós a convertemos em uma família $A$ sobre $2n$ elementos, tais que $A$ é máximo se e somente se $\Psi$em insatisfatório. O$2n$ os elementos virão em pares, que denoto por $i$ e $i'$.
O complemento de cada par está contido em$A$ não obstante $\Psi$, tão $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Além disso, para cada cláusula, adicionamos um conjunto para$A$ tal que se $x_i$ está na cláusula, o conjunto contém $i$, enquanto se $\bar x_i$ está na cláusula, o conjunto contém $i'$. Por exemplo, a cláusula$(x_i\vee \bar x_j)$ adiciona o conjunto $ij'$ para $A$.
Suponha $\Psi$é satisfazível. Então, para uma avaliação satisfatória$x$, defina o conjunto $S$ de tal modo que $i\in S$ E se $x_i$ é falso e $i'\in S$ E se $x_i$é verdade. É simples verificar se$S$ não está em relação com qualquer elemento de $A$.
Suponha que $A$não é máximo. Pegue um conjunto$S$ não em relação a qualquer elemento de $A$. Definir$x_i$ para ser verdade se $i\notin S$ e falso se $i'\notin S$, caso contrário, arbitrariamente. Esta definição é de fato correta, pois$\overline{ii'}\in A$ implica que $i,i'\in S$não é possível. É simples verificar se$x$ é uma avaliação satisfatória de $\Psi$.