Checking disjointness between subsets of a poset

Question

If there is a poset $(P, \le)$ and two sets $X \subseteq P$ and $Y \subseteq P$, and we have a way $f : P^2 \to 2$ to efficiently compute for any $(x, y) \in P^2$ whether there exists a $z \in P$ such that $(x \le z) \wedge (y \le z)$, we want to return $\mathbf{T}$ if there exists a pair $(x, y) \in X \times Y$ such that $f(x, y) = 1$ and $\mathbf{F}$ otherwise, using the fewest possible number of calls to $f$ and $\le$.

Answer 1

Without further information, you can't do any better than $O(n^2)$ queries to $f$, where $n=|X|+|Y|$. There is a simple adversary argument.

Imagine you have an algorithm that uses $o(n^2)$ queries. Consider running it on a set $X,Y$ chosen so that $f(x,y)=0$ for all $x \in X, y \in Y$. If the algorithm is correct, the algorithm must return F on this input. Since the algorithm runs in $o(n^2)$ time, there must exist some pair of elements $x_0,y_0$ that was never queried. Now run the algorithm on a pair of sets $X,Y$ chosen so that $f(x_0,y_0)=1$ but $f(x,y)=0$ for all other pairs $x,y$. We see that $f$ always returns 0 during this execution, too, so this execution must follow exactly the same path as the first execution, and thus must also return F on this input. However, returning F on this input is incorrect. Therefore, there is no algorithm that takes $o(n^2)$ time and is always correct.