Vérification de la disjonction entre les sous-ensembles d'un poset

Question

S'il y a un poset $(P, \le)$ et deux ensembles $X \subseteq P$ et $Y \subseteq P$, et nous avons un moyen $f :P^2 \à 2$ calculer efficacement pour tout $(x, y) \in P^2$ s'il existe un $z \in P$ tel que $(x \le z) \coin (y \le z)$, nous voulons revenir $\mathbf{T}$ s'il existe une paire $(x, y) \in X imes Y$ tel que $f(x, y) = 1$ et $\mathbf{F}$ sinon, en utilisant le moins d'appels possible vers $f$ et $\le$.

Answer 1

Sans plus d'informations, vous ne pouvez pas faire mieux que $O(n^2)$ requêtes à $f$, où $n=|X|+|Y|$.Il existe un simple argument adverse.

Imaginez que vous ayez un algorithme qui utilise $o(n^2)$ requêtes.Pensez à l'exécuter sur un plateau $X,Y$ choisi pour que $f(x,y)=0$ pour tous $x \dans X, y \dans Y$.Si l'algorithme est correct, l'algorithme doit renvoyer F sur cette entrée.Puisque l'algorithme s'exécute dans $o(n^2)$ temps, il doit exister une paire d'éléments $x_0,y_0$ cela n'a jamais été remis en question.Exécutez maintenant l'algorithme sur une paire d'ensembles $X,Y$ choisi pour que $f(x_0,y_0)=1$ mais $f(x,y)=0$ pour toutes les autres paires $x,y$.On voit ça $f$ renvoie toujours 0 lors de cette exécution également, donc cette exécution doit suivre exactement le même chemin que la première exécution, et doit donc également renvoyer F sur cette entrée.Cependant, renvoyer F sur cette entrée est incorrect.Il n’existe donc aucun algorithme qui prenne $o(n^2)$ temps et est toujours correct.