Comprobar la desunión entre subconjuntos de un poset

Question

Si hay un poset $(P,\le)$ y dos juegos $X \subseteq P$ y $Y \subseteq P$, y tenemos una manera $f:P^2 \a 2$ para calcular eficientemente cualquier $(x, y) \en P^2$ si existe un $z \en P$ tal que $(x \le z) \cuña (y \le z)$, queremos volver $\mathbf{T}$ si existe un par $(x, y) \en X \veces Y$ tal que $f(x, y) = 1$ y $\mathbf{F}$ de lo contrario, utilizar el menor número posible de llamadas para $f$ y $\le$.

Answer 1

Sin más información, no hay nada mejor que $O(n^2)$ consultas a $f$, dónde $n=|X|+|Y|$.Hay un simple argumento adversario.

Imagina que tienes un algoritmo que utiliza $o(n^2)$ consultas.Considere ejecutarlo en un set $X,Y$ elegido para que $f(x,y)=0$ para todos $x \en X, y \en Y$.Si el algoritmo es correcto, el algoritmo debe devolver F en esta entrada.Dado que el algoritmo se ejecuta en $o(n^2)$ tiempo, debe existir algún par de elementos $x_0,y_0$ eso nunca fue cuestionado.Ahora ejecuta el algoritmo en un par de conjuntos. $X,Y$ elegido para que $f(x_0,y_0)=1$ pero $f(x,y)=0$ para todos los demás pares $x,y$.Vemos eso $f$ También siempre devuelve 0 durante esta ejecución, por lo que esta ejecución debe seguir exactamente la misma ruta que la primera ejecución y, por lo tanto, también debe devolver F en esta entrada.Sin embargo, devolver F en esta entrada es incorrecto.Por lo tanto, no existe ningún algoritmo que tome $o(n^2)$ tiempo y siempre es correcto.