Was ist der schnellste Weg, um die Einbeziehung von Sets zu überprüfen?

Bei Teilmengen von .S 1 , … , S n { 1 , … , d $n$$S_1,\ldots,S_n$$\{1,\ldots,d\}$

Überprüfen Sie, ob es Mengen mit . (Wenn ja, finden Sie ein Beispiel, wenn nicht, sagen Sie einfach "nein".)$S_i,S_j$$S_i \subsetneq S_j$

Die triviale Lösung für dieses Problem durchläuft alle Mengenpaare und überprüft die Einbeziehung eines Paares in der Zeit , sodass die Gesamtlaufzeit O (n ^ 2 d) ist . Kann dieses Problem schneller gelöst werden? Gibt es in der Literatur einen Namen dafür?$O(d)$$O(n^2 d)$

Sie können es nicht in $O(n^{2-\epsilon})$ für eine Konstante \ epsilon> 0 lösen, es $\epsilon>0$sei denn, die Hypothese der starken exponentiellen Zeit ist falsch.

Das heißt, wenn wir einen solchen Algorithmus hätten, könnten wir $n$ variable CNF-Erfüllbarkeit in $O((2-\epsilon')^{n})$ Zeit für einige & epsi;> 0 lösen $\epsilon'>0$. Der Grund ist, dass wir die Variablen in zwei gleiche Teile $P_1$ und $P_2$ von jeweils $n/2$ Variablen teilen könnten . Für jeden Teil konstruieren wir auf folgende Weise eine Familie $F_1$ bzw. $F_2$ von Teilmengen der Klauseln. Für jede Aufgabe fügen wir eine Teilmenge hinzu, die aus den Klauseln besteht, die von der Aufgabe nicht erfüllt werden. Diese Konstruktion läuft in $poly(n)2^{n/2}$ -Zeit.

Um die Konstruktion $F_1$ , ist zu beachten, dass die ursprüngliche CNF-Instanz eine Lösung hat, wenn es eine Teilmenge in F_1 gibt, die mit einer Teilmenge in F_2 disjunkt ist $F_2$.

Wenn Sie zusätzlich zu den Elementen für jede Klausel einige zusätzliche Elemente zu Ihrer Grundmenge hinzufügen, ist es nicht allzu schwierig, dieses Disjunktitätsproblem als Frage der Mengeneinbeziehung einzubetten. Grundsätzlich nehmen Sie die Ergänzungen der Teilmengen in . Um sicherzustellen, dass zwei Sätze in nicht als Einschluss gezählt werden, fügen Sie den zusätzlichen Elementen einen Code aus einer Anti-Chain hinzu. Ein anderer Anti-Ketten-Code (für andere zusätzliche Elemente der Grundmenge) wird für die Teilmengen von , um sicherzustellen, dass kein Paar von Teilmengen von eine Einbeziehung bildet. Schließlich enthalten alle Mengen, die aus gebildet werden, alle Elemente der Anti-Ketten-Codes von .$F_1$$F_1$$F_2$$F_2$$F_1$$F_2$

Dies ist eine Mengeneinschlussfrage für Teilmengen auf einer -Grundmenge. Das Argument geht im Wesentlichen auf eine frühe Veröffentlichung von Ryan Williams zurück (ich kann mich nicht erinnern, welche).$2^{n/2+1}$$d=poly(n)$

Wenn Sie sich für Mengenfamilien mit interessieren , ist eine andere Lösung, die der in Yuvals Antwort skizzierten konzeptionell sehr ähnlich ist, die Berechnung der Zeta-Transformation$n = \omega(2^{d/2})$

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

Dabei ist die Indikatorfunktion der Eingabefamilie . Das heißt, wenn und andernfalls. Es ist klar, dass es Mengen so dass genau dann, wenn für einige .$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}$

Die Zeta-Transformation kann in der Zeit Verwendung des Yates-Algorithmus berechnet werden, siehe zum Beispiel Knuths TAOCP, vol. 2, §4.6.4. Der Algorithmus selbst ist eine recht einfache dynamische Programmierung, und es ist leicht, ihn zu ändern, um ein Beispiel für eine eingeschlossene Menge zu geben, falls eine existiert.$O(d2^d)$

Dieses Problem kann gelöst werden, indem ein Algorithmus für die schnelle Matrixmultiplikation verwendet wird, und ich vermute auch, dass er der Matrixmultiplikation rechnerisch äquivalent ist (obwohl ich keine Möglichkeit kenne, dies zu beweisen, und ich glaube nicht, dass Techniken zum Nachweis vorhanden sind ). Diese Lösung hätte eine Laufzeit von O (n ^ {2.373}), wenn n = d, und andere Laufzeiten für andere Beziehungen zwischen d und n.

So lösen Sie es mit der Matrixmultiplikation: Sie schreiben die charakteristischen Vektoren der Mengen in die Zeilen einer n-mal-d-Matrix A und die charakteristischen Vektoren der Komplemente der Mengen in die Spalten von ad-mal-n-Matrix B. Sie Dann multiplizieren Sie A mit B. Die Paare von Mengen, die sich schneiden, sind genau die Positionen des Produkts A * B, die gleich Null sind.

Die beste bekannte Laufzeit für dieses Problem finden Sie in der Veröffentlichung von Huang und Pan zu diesem Thema. Wenn ich mich richtig erinnere, wenn d groß genug wird, wird die Laufzeit das offensichtlich optimale O (nd). Für n = d haben Sie eine Laufzeit von O (n ^ {2.373}). Für andere Beziehungen von n und d erhalten Sie andere Werte. Wenn ein optimaler Algorithmus für die Rechteckmatrix-Multiplikation existiert, erhalten Sie einen Algorithmus mit der Laufzeit O (n ^ 2 + nd) für Ihr Problem. Ich vermute, es gibt keinen besseren Weg, um Ihr Problem zu lösen, aber ich bin mir keineswegs sicher.

Diese Lösung ist wahrscheinlich nicht von praktischem Nutzen, da die Konstanten dieser Algorithmen zu groß sind. Strassens Algorithmus könnte eine Verbesserung gegenüber der naiven Lösung für vernünftige Werte von n und d ergeben, aber darüber bin ich mir nicht einmal sicher. Probleme, die mit der Matrixmultiplikation zusammenhängen, scheinen jedoch selten kombinatorische Algorithmen zu haben, die besser sind als der naive Algorithmus (um mehr als polylogarithmische Faktoren). Wenn ich also raten müsste, würde ich vermuten, dass es für Ihr Problem keinen guten Algorithmus gibt ist deutlich besser als die naive, mit den heutigen Techniken.

Wenn dann wissen wir, dass die Menge keine Antichain von Sperners Lemma ist, und so ist die Entscheidungsversion des Problems wird trivial. Es könnte jedoch interessant sein, den Fall zu betrachten, in dem nahe an diesem Wert liegt.$n > \binom{d}{d/2} \approx \frac{2^d}{\sqrt{\pi d/2}}$$n$

Friedguts Arbeit zum Erdős-Ko-Rado-Theorem zeigt, dass man angesichts des charakteristischen Vektors einer Familie von Teilmengen von in der Zeit feststellen kann, ob eine sich überschneidende Familie ist (alle zwei Elemente von schneiden). Allgemeiner erlaubt uns seine Methode, zu berechnen wobei eine (spezifische) bekannte Funktion ist, die nicht Null nur, wenn disjunkt sind. hängt nur vom Histogramm von , wobei der Indikator für .$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$

(Nebenbei, wir anmerken , dass seine Methode funktioniert auch , wenn wir gegeben sind zwei Familien , und interessiert sind in . In In beiden Fällen müssen wir die verzerrten Fourier-Walsh-Transformationen von für ein beliebiges und dann , wobei nur vom Hamming-Gewicht von abhängt .)$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$

Wie hängt das alles mit dem vorliegenden Problem zusammen? Betrachten Sie die Familie Jedes ist von jedem . Da explizit angegeben ist, können wir den Beitrag dieser Paare zu berechnen . Gibt es noch mehr unzusammenhängende Paare? Wenn von dann ist und somit . Also ist ein 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\}).$$

Dieser Algorithmus läuft in der Zeit und ignoriert die polynomiellen Faktoren in . Wenn in der Nähe von , ist dies signifikant besser als . Im Allgemeinen erhalten wir eine Verbesserung, solange .$\tilde{O}(n + 2^d)$$d$$n$$2^d$$\tilde{O}(n^2)$$n = \omega(2^{d/2})$

Wenn wir wissen, dass ein Paar existiert, das , wie finden wir es? Angenommen, wir teilen alle Mengen nach dem Zufallsprinzip in zwei Gruppen auf. Mit einer Wahrscheinlichkeit von ungefähr befinden sich die Mengen und in derselben Gruppe. Wenn wir so viel Glück haben, können wir unseren Algorithmus auf und ausführen , herausfinden, zu welcher Gruppe diese gehören, und so die Anzahl der zu berücksichtigenden Mengen halbieren. Wenn nicht, können wir es erneut versuchen. Dies zeigt, dass wir mit einer erwarteten Anzahl von Orakelaufrufen zur Entscheidungsversion tatsächlich ein Paar finden können, das .$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$

Wir können den Algorithmus auch derandomisieren. Nehmen wir an, dass ohne dass die Allgemeinheit verloren geht . In jedem Schritt partitionieren wir nach jedem der Bits. Eine dieser Partitionen setzt und in denselben Teil, es sei denn, sie haben entgegengesetzte Polaritäten. Wir können dies explizit nur mit testen . Dies ergibt einen deterministischen Algorithmus, der Orakelaufrufe für die Entscheidungsversion verwendet.$n = 2^k$$k$$x$$y$$O(nd)$$O(\log^2 n)$