Verificación de un antichain máximo
En la teoría del orden, un antichain (familia Sperner / desorden) es un subconjunto de un conjunto parcialmente ordenado, con la propiedad de que no hay dos elementos comparables entre sí. Un antichain máximo es el antichain que no está contenido correctamente en otro antichain. Tomemos el conjunto de poder de$\{1,2,\ldots, n\}$como nuestro conjunto parcialmente ordenado, aquí el orden se da por inclusión. Entonces mi pregunta es, para cualquier antichain dado de este conjunto parcialmente ordenado, ¿existe algún algoritmo de tiempo polinómico (con respecto a$n$) para verificar que este antichain es realmente "máximo"? En otras palabras, verificar que cualquier subconjunto de$\{1,2,\ldots, n\}$está contenido o contiene algún conjunto del antichain. Aquí, dicho algoritmo debería tener un tiempo de ejecución polinomial para CUALQUIER antichain.
Actualización : Para aclarar, aquí trataré el tamaño de nuestro antichain como el parámetro para el algoritmo de verificación. En otras palabras, mi pregunta es: ¿existe un algoritmo de verificación, cuyo tiempo de ejecución es polinomial en$n$ y $m$, dónde $m$es el tamaño del antichain. Cuando el tamaño de nuestro antichain$m$ es exponencial en $n$entonces dicho algoritmo es trivial (simplemente comparando esos elementos uno por uno); pero cuando el antichain dado tiene tamaño O (poli (n)), este es mi caso interesado. Por ejemplo, cuando el antichain es dado por$\{\{1\}, \ldots, \{n\}\}$, ciertamente no tenemos que hacer la comparación de fuerza bruta.
Respuestas
Observación. Originalmente dije que esto era una solución completa, pero eso era falso, como lo demostró Emil en los comentarios. Sin embargo, este argumento prueba la siguiente versión más débil.
Puedo demostrar que es co-NP-completo decidir por una familia de entrada $A$ si hay un conjunto $S$ que no está relacionado con todos los conjuntos en $A$. Llamaré máximas a esas familias. Esto muestra que cualquier posible algoritmo de tiempo polinomial debe aprovechar que la familia de entrada es un antichain, ya para entradas de tamaño lineal. Mi reducción es del SAT.
Dado un CNF $\Psi$ en $n$ variables, lo convertimos en una familia $A$ encima $2n$ elementos, tales que $A$ es máxima si y solo si $\Psi$en insatisfactorio. La$2n$ los elementos vendrán en pares, que denoto por $i$ y $i'$.
El complemento de cada par está contenido en$A$ a pesar de $\Psi$, entonces $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Además, para cada cláusula agregamos un conjunto a$A$ tal que si $x_i$ está en la cláusula, el conjunto contiene $i$, mientras que si $\bar x_i$ está en la cláusula, el conjunto contiene $i'$. Por ejemplo, la cláusula$(x_i\vee \bar x_j)$ agrega el conjunto $ij'$ a $A$.
Suponer $\Psi$es satisfactorio. Entonces para una evaluación satisfactoria$x$, define el conjunto $S$ tal que $i\in S$ Si $x_i$ es falso y $i'\in S$ Si $x_i$es verdad. Es sencillo comprobar que$S$ no está en relación con ningún elemento de $A$.
Suponer que $A$no es máxima. Tomar un juego$S$ no en relación con ningún elemento de $A$. Definir$x_i$ para ser verdad si $i\notin S$ y falso si $i'\notin S$, de lo contrario arbitrariamente. Esta definición es de hecho correcta, ya que$\overline{ii'}\in A$ implica que $i,i'\in S$no es posible. Es sencillo comprobar que$x$ es una evaluación satisfactoria de $\Psi$.