Quel est le moyen le plus rapide de vérifier l'inclusion d'un ensemble?

Étant donné sous-ensembles de .$n$$S_1,\ldots,S_n$$\{1,\ldots,d\}$

Vérifiez s'il existe des ensembles avec . (Si oui, trouvez un exemple, sinon, dites simplement «non»)$S_i,S_j$$S_i \subsetneq S_j$

La solution triviale à ce problème passe par toutes les paires d'ensembles et vérifie l'inclusion d'une paire dans le temps $O(d)$ , donc le temps d'exécution global est $O(n^2 d)$ . Ce problème peut-il être résolu plus rapidement? Y a-t-il un nom pour cela dans la littérature?

Vous ne pouvez pas le résoudre en temps $O(n^{2-\epsilon})$ pour une constante $\epsilon>0$ sauf si l' hypothèse de temps exponentiel fort est fausse.

Autrement dit, si nous avions un tel algorithme, nous pourrions résoudre une satisfaction CNF à $n$ variables en temps $O((2-\epsilon')^{n})$ pour un certain $\epsilon'>0$ . La raison en est que nous pourrions diviser les variables en deux parties égales $P_1$ et $P_2$ de $n/2$ variables chacune. Pour chaque partie on construit une famille $F_1$ et $F_2$ respectivement de sous-ensembles des clauses de la manière suivante. Pour chaque affectation, nous ajoutons un sous-ensemble composé des clauses non satisfaites par l'affectation. Cette construction s'exécute en temps $poly(n)2^{n/2}$ .

Pour terminer la construction, nous notons que l'instance CNF d'origine a une solution ssi il y a un sous-ensemble dans $F_1$ qui est disjoint à un sous-ensemble dans $F_2$ .

En ajoutant des éléments supplémentaires à votre ensemble de terrain en plus de ceux de chaque clause, il n'est pas trop difficile d'incorporer ce problème de disjonction comme une question d'inclusion d'ensemble. Vous prenez essentiellement les compléments des sous-ensembles dans . Pour vous assurer que deux ensembles dans ne sont pas comptés comme une inclusion, vous ajoutez un code d'une anti-chaîne sur les éléments supplémentaires. Un autre code anti-chaîne (sur d'autres éléments supplémentaires de l'ensemble de masse) est utilisé sur les sous-ensembles de pour s'assurer qu'aucune paire de sous-ensembles de forme une inclusion. Enfin, tous les ensembles formés à partir de comprennent tous les éléments des codes anti-chaîne de .$F_1$$F_1$$F_2$$F_2$$F_1$$F_2$

Il s'agit d'une question d'inclusion d'ensemble sur sous-ensembles sur un ensemble de masse . L'argument remonte essentiellement à un des premiers articles de Ryan Williams (je ne me souviens plus lequel).$2^{n/2+1}$$d=poly(n)$

Si vous êtes intéressé par les familles d'ensembles avec , alors une autre solution conceptuellement très similaire à celle décrite dans la réponse de Yuval est de calculer la transformation zêta$n = \omega(2^{d/2})$

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

où est la fonction d'indicateur de la famille d'entrée . Autrement dit, si et sinon. Il existe clairement des ensembles tels que si et seulement si pour certains .$f \colon 2^{[d]} \to \mathbb{R}$$\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 transformée zêta peut être calculée dans le temps utilisant l'algorithme de Yates, voir par exemple TAOCP de Knuth, vol. 2, §4.6.4. L'algorithme lui-même est une programmation dynamique assez simple, et il est facile de le modifier pour donner un exemple d'un ensemble inclus s'il en existe un.$O(d2^d)$

Ce problème peut être résolu en utilisant un algorithme de multiplication matricielle rapide, et je soupçonne également qu'il est équivalent sur le plan informatique à la multiplication matricielle (bien que je ne connaisse aucun moyen de le prouver, et je ne pense pas que des techniques pour le prouver existent ). Cette solution aurait un temps d'exécution de O (n ^ {2.373}) lorsque n = d, et d'autres temps d'exécution pour d'autres relations entre d et n.

Voici comment vous le résolvez en utilisant la multiplication matricielle: vous écrivez les vecteurs caractéristiques des ensembles dans les rangées d'une matrice n par d A, et les vecteurs caractéristiques des compléments des ensembles dans les colonnes de ad par n matrice B. Vous multipliez ensuite A par B. Les paires d'ensembles qui se croisent sont exactement les emplacements du produit A * B qui sont égaux à zéro.

Pour la meilleure durée de fonctionnement connue pour ce problème, voir l'article de Huang et Pan sur le sujet. Si je me souviens bien, lorsque d devient suffisamment grand, le temps de fonctionnement deviendra l'O (nd) évidemment optimal. Pour n = d, vous aurez un temps d'exécution de O (n ^ {2.373}). Pour les autres relations de n et d, vous obtiendrez d'autres valeurs. Si un algorithme optimal pour la multiplication de matrice rectangulaire existe, vous obtiendrez un algorithme avec le temps d'exécution O (n ^ 2 + nd) pour votre problème. Je soupçonne qu'il n'y a pas de meilleur moyen que celui-ci pour résoudre votre problème, mais je suis loin d'être sûr.

Cette solution n'est probablement pas d'une utilité pratique, car les constantes de ces algorithmes sont trop grandes. L'algorithme de Strassen pourrait apporter une amélioration par rapport à la solution naïve pour des valeurs raisonnables de n et d, mais je n'en suis même pas sûr. Cependant, les problèmes qui semblent si liés à la multiplication matricielle semblent rarement avoir des algorithmes combinatoires qui sont meilleurs que l'algorithme naïf (par plus de facteurs polylogarithmiques), donc si je devais deviner, je suppose qu'il n'y a pas de bon algorithme pour votre problème qui est nettement meilleure que la naïve, en utilisant les techniques actuelles.

Si alors nous savons que l'ensemble n'est pas une antichaine par le lemme de Sperner, et donc le la version de décision du problème devient triviale. Mais il pourrait être intéressant de considérer le cas où est proche de cette valeur.$n > \binom{d}{d/2} \approx \frac{2^d}{\sqrt{\pi d/2}}$$n$

Les travaux de Friedgut sur le théorème d'Erdős-Ko-Rado montrent que, étant donné le vecteur caractéristique d'une famille de sous-ensembles de , on peut trouver dans le temps si est une famille qui se recoupe (tous les deux éléments de couper). Plus généralement, sa méthode nous permet de calculer où est une fonction connue (spécifique) qui n'est pas zéro uniquement si sont disjoints. ne dépend que de l'histogramme de , où est l'indicateur 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$

(En passant, nous commentons que sa méthode fonctionne également si on nous donne deux familles et que nous sommes intéressés par . dans les deux cas, nous devons calculer les transformées de Fourier-Walsh à biais de pour un arbitraire , puis , où ne dépend que du poids 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$

Comment tout cela est-il lié au problème actuel? Considérons la famille Chaque est disjoint de chaque . Puisque est donné explicitement, nous pouvons calculer la contribution de ces paires à . Y a-t-il d'autres paires disjointes? Si est de alors et donc . Donc est 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\}).$$

Cet algorithme s'exécute dans le temps , en ignorant les facteurs polynomiaux en . Lorsque est proche de , c'est nettement mieux que . En général, nous obtenons une amélioration tant que .$\tilde{O}(n + 2^d)$$d$$n$$2^d$$\tilde{O}(n^2)$$n = \omega(2^{d/2})$

Étant donné que nous savons qu'il existe une paire satisfaisant , comment la trouver? Supposons que nous divisions tous les ensembles en deux groupes au hasard. Avec une probabilité d'environ , les ensembles et se retrouveront dans le même groupe. Si nous sommes si chanceux, nous pouvons exécuter notre algorithme sur et , trouver à qui appartiennent-ils, et ainsi diviser par deux le nombre d'ensembles que nous devons considérer. Sinon, nous pouvons réessayer. Cela montre qu'avec un nombre attendu d' appels oracle à la version de décision, nous pouvons réellement trouver une paire satisfaisant .$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$

Nous pouvons également dérandomiser l'algorithme. Sans perte de généralité, supposons . À chaque étape, nous partitionnons en fonction de chacun des bits. Une de ces partitions mettra toujours et dans la même partie, sauf si elles ont des polarités opposées; nous pouvons tester cela explicitement en utilisant uniquement des opérations . Cela donne un algorithme déterministe utilisant appels oracle à la version de décision.$n = 2^k$$k$$x$$y$$O(nd)$$O(\log^2 n)$