Überprüfen der Disjunktheit zwischen Teilmengen eines Posets

Question

Wenn es ein Poset gibt $(P, \le)$ und zwei Sätze $X \subseteq P$ Und $Y \subseteq P$, und wir haben einen Weg $f :P^2 \zu 2$ für jeden effizient berechnen $(x, y) \in P^2$ ob es eine gibt $z \in P$ so dass $(x \le z) \wedge (y \le z)$, wir wollen zurückkehren $\mathbf{T}$ wenn es ein Paar gibt $(x, y) \in X imes Y$ so dass $f(x, y) = 1$ Und $\mathbf{F}$ andernfalls wird die geringstmögliche Anzahl an Aufrufen verwendet $f$ Und $\le$.

Answer 1

Ohne weitere Informationen können Sie es nicht besser machen $O(n^2)$ Anfragen an $f$, Wo $n=|X|+|Y|$.Es gibt ein einfaches Gegnerargument.

Stellen Sie sich vor, Sie haben einen Algorithmus, der verwendet $o(n^2)$ Abfragen.Erwägen Sie, es auf einem Set auszuführen $X,Y$ so gewählt, dass $f(x,y)=0$ für alle $x \in X, y \in Y$.Wenn der Algorithmus korrekt ist, muss der Algorithmus F für diese Eingabe zurückgeben.Da läuft der Algorithmus ein $o(n^2)$ Zeit muss es ein Elementpaar geben $x_0,y_0$ das wurde nie abgefragt.Führen Sie nun den Algorithmus für ein Mengenpaar aus $X,Y$ so gewählt, dass $f(x_0,y_0)=1$ Aber $f(x,y)=0$ für alle anderen Paare $x,y$.Wir sehen das $f$ Auch bei dieser Ausführung wird immer 0 zurückgegeben, daher muss diese Ausführung genau dem gleichen Pfad wie die erste Ausführung folgen und daher auch bei dieser Eingabe F zurückgeben.Die Rückgabe von F für diese Eingabe ist jedoch falsch.Daher gibt es keinen Algorithmus, der dies übernimmt $o(n^2)$ Zeit und ist immer richtig.