Controllo della disgiunzione tra sottoinsiemi di un poset

Question

Se c'è un poset $(P, \le)$ e due set $X \subseteq P$ E $Y \subseteq P$, e abbiamo un modo $f:P^2 \a 2$ per calcolare in modo efficiente qualsiasi $(x, y) \in P^2$ se esiste a $z \inP$ tale che $(x \le z) \cuneo (y \le z)$, vogliamo tornare $\mathbf{T}$ se esiste una coppia $(x, y) \in X imes Y$ tale che $f(x, y) = 1$ E $\mathbf{F}$ in caso contrario, utilizzando il minor numero possibile di chiamate a $f$ E $\le$.

Answer 1

Senza ulteriori informazioni, non puoi fare di meglio di $O(n^2)$ domande a $f$, Dove $n=|X|+|Y|$.C'è un semplice argomento avversario.

Immagina di avere un algoritmo che utilizza $o(n^2)$ interrogazioni.Considera l'idea di eseguirlo su un set $X,Y$ scelto così $f(x,y)=0$ per tutti $x \in X, y \in Y$.Se l'algoritmo è corretto, l'algoritmo deve restituire F su questo input.Poiché l'algoritmo viene eseguito $o(n^2)$ volta, deve esistere una coppia di elementi $x_0,y_0$ questo non è mai stato messo in discussione.Ora esegui l'algoritmo su una coppia di insiemi $X,Y$ scelto così $f(x_0,y_0)=1$ Ma $f(x,y)=0$ per tutte le altre coppie $x,y$.Lo vediamo $f$ restituisce sempre 0 anche durante questa esecuzione, quindi questa esecuzione deve seguire esattamente lo stesso percorso della prima esecuzione e quindi deve restituire anche F su questo input.Tuttavia, restituire F su questo input non è corretto.Pertanto, non esiste un algoritmo che lo prenda $o(n^2)$ tempo ed è sempre corretto.