¿Cuál es la forma más rápida de verificar la inclusión de conjuntos?

Dados subconjuntos de .S 1 , ... , S n { 1 , ... , d $n$$S_1,\ldots,S_n$$\{1,\ldots,d\}$

Compruebe si hay conjuntos con . (Si es así, encuentre un ejemplo, si no, simplemente diga "no")$S_i,S_j$$S_i \subsetneq S_j$

La solución trivial a este problema pasa por todos los pares de conjuntos y verifica la inclusión de un par en el tiempo $O(d)$ , por lo que el tiempo de ejecución general es $O(n^2 d)$ . ¿Se puede resolver este problema más rápido? ¿Hay un nombre para eso en la literatura?

No puede resolverlo en tiempo $O(n^{2-\epsilon})$ para cualquier constante $\epsilon>0$ menos que la Hipótesis de tiempo exponencial fuerte sea ​​falsa.

Es decir, si tuviéramos un algoritmo tal, podríamos resolver $n$ -Variable CNF satisfacibilidad en $O((2-\epsilon')^{n})$ de tiempo para algunos $\epsilon'>0$ . La razón es que podríamos dividir las variables en dos partes iguales $P_1$ y $P_2$ de $n/2$ variables cada una. Para cada parte construimos una familia $F_1$ y $F_2$ respectivamente de subconjuntos de las cláusulas de la siguiente manera. Para cada tarea, agregamos un subconjunto que consta de las cláusulas que la tarea no satisface. Esta construcción se ejecuta en $poly(n)2^{n/2}$ veces.

Para finalizar la construcción, observamos que la instancia original de CNF tiene una solución si hay un subconjunto en $F_1$ que es disjunto de algún subconjunto en $F_2$ .

Al agregar algunos elementos adicionales a su conjunto de bases además de los de cada cláusula, no es demasiado difícil incorporar este problema de disyunción como una cuestión de inclusión de conjuntos. Básicamente, toma los complementos de los subconjuntos en . Para asegurarse de que dos conjuntos en no se cuenten como una inclusión, agregue un código de una cadena anti en los elementos adicionales. Se utiliza otro código anti-cadena (en otros elementos adicionales del conjunto ) en los subconjuntos de para asegurarse de que ningún par de subconjuntos de forme una inclusión. Finalmente, todos los conjuntos formados a partir de incluyen todos los elementos de los anti-cadena de .$F_1$$F_1$$F_2$$F_2$$F_1$$F_2$

Esta es una pregunta de inclusión de conjuntos en subconjuntos en un conjunto base . El argumento básicamente se remonta a algunos de los primeros artículos de Ryan Williams (no recuerdo cuál).$2^{n/2+1}$$d=poly(n)$

Si está interesado en establecer familias con , entonces otra solución conceptualmente muy similar a la descrita en la respuesta de Yuval es calcular la transformación zeta$n = \omega(2^{d/2})$

$$f\zeta(T) = \sum_{S \subseteq T} f(S)\,,$$

donde es la función del indicador de la familia de entrada . Es decir, si y contrario. Claramente, hay conjuntos tales que si y solo si para algunos .$f \colon 2^{[d]} \to \mathbb{R}$f ( S ) = 1 S ∈ F f ( S ) = 0 S i ≠ S j S i ⊆ S j f ζ ( S ) > 1 S ∈ $\mathcal{F} = \{ S_1, S_2, \dotsc, S_n \}$$f(S) = 1$$S \in \mathcal{F}$$f(S) = 0$$S_i \not= S_j$$S_i \subseteq S_j$$f\zeta(S) > 1$$S \in \mathcal{F}$

La transformación zeta se puede calcular en el tiempo utilizando el algoritmo de Yates, véase, por ejemplo, TAOCP de Knuth, vol. 2, §4.6.4. El algoritmo en sí mismo es una programación dinámica bastante sencilla, y es fácil modificarlo para dar un ejemplo de un conjunto incluido si existe.$O(d2^d)$

Este problema se puede resolver mediante el uso de un algoritmo para la multiplicación rápida de matrices, y también sospecho que es computacionalmente equivalente a la multiplicación matricial (aunque no conozco ninguna forma de demostrarlo, y no creo que existan técnicas para demostrarlo). ) Esta solución tendría un tiempo de ejecución de O (n ^ {2.373}) cuando n = d, y otros tiempos de ejecución para otras relaciones entre d y n.

Así es como lo resuelve usando la multiplicación de matrices: escribe los vectores característicos de los conjuntos en las filas de una matriz n por d A, y los vectores característicos de los complementos de los conjuntos en las columnas de ad por n matriz B. luego multiplique A por B. Los pares de conjuntos que se cruzan son exactamente las ubicaciones del producto A * B que son iguales a cero.

Para conocer el mejor tiempo de ejecución conocido para este problema, consulte el documento de Huang y Pan sobre el tema. Si no recuerdo mal, cuando d se vuelve lo suficientemente grande, el tiempo de ejecución se convertirá en el O (nd) obviamente óptimo. Para n = d, tendrá un tiempo de ejecución de O (n ^ {2.373}). Para otras relaciones de n y d, obtendrá otros valores. Si existe un algoritmo óptimo para la multiplicación de matriz rectangular, obtendrá un algoritmo con tiempo de ejecución O (n ^ 2 + nd) para su problema. Sospecho que no hay mejor manera que esta para resolver su problema, pero no estoy seguro.

Esta solución probablemente no sea de uso práctico, ya que las constantes de estos algoritmos son demasiado grandes. El algoritmo de Strassen podría proporcionar una mejora sobre la solución ingenua para valores razonables de nyd, pero ni siquiera estoy seguro de eso. Sin embargo, los problemas que parecen tan relacionados con la multiplicación de matrices rara vez parecen tener algoritmos combinatorios que son mejores que el algoritmo ingenuo (por más que factores poliligarítmicos), por lo que si tuviera que adivinar, supongo que no hay un buen algoritmo para su problema que es significativamente mejor que el ingenuo, usando técnicas actuales.

Si entonces sabemos que el conjunto no es un antichain por el lema de Sperner, por lo que el La versión de decisión del problema se vuelve trivial. Pero podría ser interesante considerar el caso donde está cerca de ese valor.$n > \binom{d}{d/2} \approx \frac{2^d}{\sqrt{\pi d/2}}$$n$

El trabajo de Friedgut sobre el teorema de Erdős-Ko-Rado muestra que dado el vector característico de una familia de subconjuntos de , uno puede encontrar en el tiempo si es una familia que se cruza (cada dos elementos de intersecarse). En términos más generales, su método nos permite calcular donde es alguna función conocida (específica) que no es cero solo si son disjuntos. depende solo del histograma de , donde es el indicador de .$f$$[m]$$O(m2^m)$$f$$f$

$$\Sigma = \sum_{x,y \in f} S(x,y),$$ $S(x,y) \geq 0$$x,y$$S(x,y)$$\{(x_i,y_i) : i \in [d]\}$$x_i$$i \in x$

(Como comentario, comentamos que su método también funciona si se nos dan dos familias , y estamos interesados ​​en . En ambos casos, debemos calcular las transformadas de Fourier-Walsh sesgadas de para una arbitraria , y luego , donde depende solo del peso de Hamming de .)$f,g$$\Sigma = \sum_{x\in f, y\in g} S(x,y)$$p$$f,g$$p \in (0,1/2)$$\Sigma = \sum_x T(x) \hat{f}(x) \hat{g}(x)$$T(x)$$x$

¿Cómo se relaciona todo esto con el problema en cuestión? Considere la familia Cada es disjunto de cada . Dado que se da explícitamente, podemos calcular la contribución de estos pares a . ¿Hay más pares disjuntos? Si es disjunto de entonces y entonces . Entonces es un antichain iff

$$F = \{ S_i \cup \{x\} : i \in [n] \} \cup \{ \overline{S_i} \cup \{y\} : i \in [n] \}.$$ $S_i \cup \{x\}$$\overline{S_i} \cup \{y\}$$S(x,y)$$\Sigma$$S_i \cup \{x\}$$\overline{S_j} \cup \{y\}$$S_i \cap \overline{S_j} = \emptyset$$S_i \subseteq S_j$$S_1,\ldots,S_n$ $$\Sigma = \sum_{i=1}^n S(S_i \cup \{x\}, \overline{S_i} \cup \{y\}).$$

Este algoritmo se ejecuta en tiempo , ignorando los factores polinómicos en . Cuando está cerca de , esto es significativamente mejor que . En general, obtenemos una mejora siempre que .$\tilde{O}(n + 2^d)$$d$$n$$2^d$$\tilde{O}(n^2)$$n = \omega(2^{d/2})$

Dado que sabemos que existe un par que satisface , ¿cómo lo encontramos? Supongamos que dividimos todos los conjuntos en dos grupos al azar. Con una probabilidad de aproximadamente , los conjuntos y se encontrarán en el mismo grupo. Si tenemos tanta suerte, podemos ejecutar nuestro algoritmo en y , encontrar a cuál pertenecen y reducir a la mitad el número de conjuntos que debemos tener en cuenta. Si no, podemos intentarlo de nuevo. Esto muestra que con un número esperado de llamadas de oráculo a la versión de decisión, podemos encontrar un par que satisfaga .$S_i \subseteq S_j$$S_1,\ldots,S_n$$G_1,G_2$$1/2$$S_i$$S_j$$G_1$$G_2$$O(\log n)$$S_i \subseteq S_j$

También podemos desrandomizar el algoritmo. Sin pérdida de generalidad, supongamos que . En cada paso, dividimos de acuerdo con cada uno de los bits. Una de estas particiones siempre pondrá e en la misma parte, a menos que tengan polaridades opuestas; podemos probar esto explícitamente usando solo operaciones . Esto proporciona un algoritmo determinista que utiliza llamadas Oracle a la versión de decisión.$n = 2^k$$k$$x$$y$$O(nd)$$O(\log^2 n)$