# Checking disjointness between subsets of a poset

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$$.

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.
• I modified the question to make it clear that $\le$ is also a valid query. – taktoa Jan 27 '20 at 3:31
• Though I guess you could always implement $x \le y$ as $f(x, y) \stackrel{?}{=} y$. – taktoa Jan 27 '20 at 3:40
• @taktoa, I am choosing inputs that are the worst case, so I have chosen them so that they are indistinguishable. Note that there exists a poset that is consistent with the two inputs I suggest. Allowing $\le$ queries does not change the result I list here. – D.W. Jan 27 '20 at 4:26