Jaki jest najszybszy sposób sprawdzenia włączenia zestawu?

Biorąc pod uwagę podzbiorów z .$n$$S_1,\ldots,S_n$$\{1,\ldots,d\}$

Sprawdź, czy istnieją zestawy z . (Jeśli tak, znajdź przykład, jeśli nie, po prostu powiedz „nie”)$S_i,S_j$$S_i \subsetneq S_j$

Trywialne rozwiązanie tego problemu polega na przejściu wszystkich par zestawów i sprawdza włączenie pary w czasie , więc całkowity czas działania wynosi . Czy ten problem można rozwiązać szybciej? Czy w literaturze jest jakaś nazwa?$O(d)$$O(n^2 d)$

Nie można go rozwiązać w czasie dla dowolnej stałej chyba że hipoteza silnego czasu wykładniczego jest fałszywa.$O(n^{2-\epsilon})$$\epsilon>0$

To znaczy, gdybyśmy mieli taki algorytm, moglibyśmy rozwiązać -zmienną satysfakcję CNF w czasie dla pewnego . Powodem jest to, że możemy podzielić zmienne na dwie równe części i po zmiennych każda. Dla każdej części konstruujemy odpowiednio rodzinę i podzbiorów klauzul w następujący sposób. Do każdego zadania dodajemy podzbiór składający się z klauzul, których przypisanie nie spełnia. Ta konstrukcja działa w czasie .$n$$O((2-\epsilon')^{n})$$\epsilon'>0$$P_1$$P_2$$n/2$$F_1$$F_2$$poly(n)2^{n/2}$

Aby zakończyć budowę, zauważamy, że oryginalna instancja CNF ma rozwiązanie, jeśli istnieje podzbiór w który jest rozłączny z jakimś podzbiorem w .$F_1$$F_2$

Dodając dodatkowe elementy do zestawu podstawowego oprócz elementów dla każdej klauzuli, nie jest zbyt trudno osadzić ten problem rozłączności jako kwestię włączenia zestawu. Zasadniczo bierzesz uzupełnienia podzbiorów w . Aby upewnić się, że dwa zestawy w nie są liczone jako włączenie, dodajesz kod z anty-łańcucha do dodatkowych elementów. Inny podzbiór łańcucha (na innych dodatkowych elementach zestawu naziemnego) jest stosowany w podzestawach aby upewnić się, że żadna para podzbiorów z tworzy włączenia. Wreszcie wszystkie zestawy utworzone z zawierają wszystkie elementy anty-łańcuchowych .$F_1$$F_1$$F_2$$F_2$$F_1$$F_2$

To jest pytanie dotyczące zestawu dla podzbiorów na zestawie podstawowym . Argument w zasadzie wraca do wczesnej gazety Ryana Williamsa (nie pamiętam, która).$2^{n/2+1}$$d=poly(n)$

Jeśli jesteś zainteresowany zestawem rodzin o $n = \omega(2^{d/2})$ , to innym rozwiązaniem koncepcyjnie bardzo podobnym do tego przedstawionego w odpowiedzi Yuvala jest obliczenie transformacji zeta

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

gdzie $f \colon 2^{[d]} \to \mathbb{R}$ jest funkcją wskaźnika rodziny wejściowej $\mathcal{F} = \{ S_1, S_2, \dotsc, S_n \}$ . To znaczy, że $f(S) = 1$ jeśli $S \in \mathcal{F}$ i $f(S) = 0$ inaczej. Oczywiście istnieją zestawy $S_i \not= S_j$ w taki sposób, $S_i \subseteq S_j$ wtedy i tylko wtedy, gdy$f\zeta(S) > 1$ z jakiegoś$S \in \mathcal{F}$ .

Transformację zeta można obliczyć w czasie $O(d2^d)$ przy użyciu algorytmu Yatesa, patrz na przykład TAOCP Knutha, t. 2, pkt 4.6.4. Sam algorytm jest dość prostym programowaniem dynamicznym i można go łatwo zmodyfikować, aby podał przykład dołączonego zestawu, jeśli taki istnieje.

Problem ten można rozwiązać za pomocą algorytmu szybkiego mnożenia macierzy, a także podejrzewam, że jest on obliczeniowo równoważny mnożeniu macierzy (chociaż nie znam żadnego sposobu, aby to udowodnić, i nie sądzę, aby istniały techniki udowodnienia tego. ). To rozwiązanie miałoby czas działania O (n ^ {2.373}), gdy n = d, oraz inne czasy działania dla innych relacji między d i n.

Oto jak to rozwiązać za pomocą mnożenia macierzy: Piszemy charakterystyczne wektory zbiorów w rzędach macierzy n przez d macierzy A, a wektory charakterystyczne uzupełnień zbiorów w kolumnach reklamy przez n macierzy B. następnie pomnóż A przez B. Przecinające się pary zbiorów to dokładnie położenia produktu A * B, które są równe zero.

Najlepszy czas działania znany z tego problemu można znaleźć w artykule Huanga i Pan na ten temat. Jeśli dobrze pamiętam, kiedy d stanie się wystarczająco duże, czas działania stanie się oczywiście optymalnym O (nd). Dla n = d będziesz mieć czas działania O (n ^ {2.373}). Dla innych relacji nid dostaniesz inne wartości. Jeśli istnieje optymalny algorytm mnożenia macierzy prostokątnej, otrzymasz algorytm z czasem wykonania O (n ^ 2 + nd) dla twojego problemu. Podejrzewam, że nie ma lepszego sposobu na rozwiązanie twojego problemu, ale nie jestem pewien.

To rozwiązanie prawdopodobnie nie ma praktycznego zastosowania, ponieważ stałe tych algorytmów są zbyt duże. Algorytm Strassena może poprawić w stosunku do naiwnego rozwiązania dla rozsądnych wartości ni id, ale nie jestem nawet tego pewien. Jednak problemy, które wydają się tak związane z mnożeniem macierzy, wydają się rzadko mieć algorytmy kombinatoryczne, które są lepsze niż algorytm naiwny (o więcej niż czynniki polilogarytmiczne), więc gdybym musiał zgadywać, zgadłbym, że nie ma dobrego algorytmu dla twojego problemu, który jest znacznie lepszy niż naiwny, z wykorzystaniem współczesnych technik.

Jeśli to wiemy, że zbiór nie jest antychainem lematu Spernera, więc wersja decyzyjna problemu staje się trywialna. Interesujące może być rozważenie przypadku, w którymnjest bliskie tej wartości.$n > \binom{d}{d/2} \approx \frac{2^d}{\sqrt{\pi d/2}}$$n$

Praca Friedguta nad twierdzeniem Erdősa-Ko-Rado pokazuje, że biorąc pod uwagę charakterystyczny wektor rodziny podzbiorów [ m ] , w czasie O ( m 2 m ) można stwierdzić, czy f jest rodziną przecinającą się (co dwa elementy f krzyżować). Mówiąc bardziej ogólnie, jego metoda pozwala obliczyć Σ = ∑ x , y ∈ f S ( x , y ) , gdzie S ( x , y ) ≥ $f$$[m]$$O(m2^m)$$f$$f$

$$\Sigma = \sum_{x,y \in f} S(x,y),$$ $S(x,y) \geq 0$jest pewną (specyficzną) znaną funkcją, która jest niezerowa tylko wtedy , gdy są rozłączne. S ( x , y ) zależy tylko od histogramu { ( x i , y i ) : i ∈ [ d ] } , gdzie x i jest wskaźnikiem dla i ∈ x .$x,y$$S(x,y)$$\{(x_i,y_i) : i \in [d]\}$$x_i$$i \in x$

(Nawiasem mówiąc, komentujemy, że jego metoda działa również, jeśli otrzymamy dwie rodziny i jesteśmy zainteresowani Σ = ∑ x ∈ f , y ∈ g S ( x , y ) . W obu przypadkach musimy obliczyć P -skewed transformat Fouriera Walsha z f , g do dowolnego p ∈ ( 0 , 1 / 2 ) , a następnie Σ = Σ x T ( x $f,g$$\Sigma = \sum_{x\in f, y\in g} S(x,y)$$p$$f,g$$p \in (0,1/2)$, gdzieT(x)zależy tylko od masy Hammingax).$\Sigma = \sum_x T(x) \hat{f}(x) \hat{g}(x)$$T(x)$$x$

Jak to wszystko ma się do problemu? Rozważ rodzinę Każdy S i ∪ { x } jest odłączony od każdego ¯ S ı ∪ { a } . Ponieważ S ( x

$$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\}$ podano wyraźnie, możemy obliczyć udział tych par w Σ . Czy są jeszcze jakieś rozłączne pary? Jeśli S i ∪ { x } jest rozłączny od ¯ S j ∪ { y }, to S i ∩ ¯ S j = ∅, a więc S i ⊆ S j . Więc S 1 , … , S n jest antychainem iff Σ = n ∑ i $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\}).$$

Algorytm działa w czasie , ignorując czynniki wielomianowe w d . Gdy n jest bliskie 2 d , jest to znacznie lepsze niż ˜ O ( n 2 ) . Zasadniczo uzyskujemy poprawę, o ile n = ω ( 2 d / 2 ) .$\tilde{O}(n + 2^d)$$d$$n$$2^d$$\tilde{O}(n^2)$$n = \omega(2^{d/2})$

Biorąc pod uwagę, że wiemy, że para spełniających istnieje, jak go znaleźć? Załóżmy, że dzielimy wszystkie zbiory S 1 , … , S n na dwie grupy G 1 , G 2 losowo. Z prawdopodobieństwem w przybliżeniu 1 / 2 , zestawy S i i S J znajdują się w tej samej grupie. Jeśli mamy szczęście, możemy uruchomić nasz algorytm na G 1 i G $S_i \subseteq S_j$$S_1,\ldots,S_n$$G_1,G_2$$1/2$$S_i$$S_j$$G_1$$G_2$, znajdź, do którego one należą, i zmniejsz o połowę liczbę zestawów, które musimy wziąć pod uwagę. Jeśli nie, możemy spróbować ponownie. To pokazuje, że przy oczekiwanej liczbie wywołań wyroczni do wersji decyzyjnej możemy faktycznie znaleźć parę spełniającą S i ⊆ S j .$O(\log n)$$S_i \subseteq S_j$

Możemy również derandomizować algorytm. Bez utraty ogólności załóżmy, że . Na każdym etapie dzielimy zgodnie z każdym z bitów k . Jeden z tych partycji zawsze położy X i Y w tej samej części, chyba że mają przeciwne bieguny; możemy to sprawdzić bezpośrednio, używając tylko operacji O ( n d ) . Daje to deterministyczny algorytm wykorzystujący wywołania O ( log 2 n ) do wersji decyzyjnej.$n = 2^k$$k$$x$$y$$O(nd)$$O(\log^2 n)$