3
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I don't understand why the execution of f on the second X, Y must follow the same path as the first X, Y. That seems to presuppose that all the elements of X and Y are completely indistinguishable, when in reality X and Y are already equipped with poset structure. $\endgroup$ – taktoa Jan 27 '20 at 2:39
  • $\begingroup$ I meant the execution of the algorithm, not of f. $\endgroup$ – taktoa Jan 27 '20 at 3:13
  • $\begingroup$ I modified the question to make it clear that $\le$ is also a valid query. $\endgroup$ – taktoa Jan 27 '20 at 3:31
  • $\begingroup$ Though I guess you could always implement $x \le y$ as $f(x, y) \stackrel{?}{=} y$. $\endgroup$ – taktoa Jan 27 '20 at 3:40
  • $\begingroup$ @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. $\endgroup$ – D.W. Jan 27 '20 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.