Verificando a disjunção entre subconjuntos de um poset

Question

Se houver um poset $(P,\le)$ e dois conjuntos $X \subseteq P$ e $Y \subseteq P$, e temos uma maneira $f:P^2 \para 2$ para calcular eficientemente qualquer $(x,y) em P^2$ se existe um $z\emP$ de tal modo que $(x \le z) \cunha (y \le z)$, queremos voltar $\mathbf{T}$ se existe um par $(x, y) \em X \vezes Y$ de tal modo que $f(x,y) = 1$ e $\mathbf{F}$ caso contrário, usando o menor número possível de chamadas para $f$ e $\le$.

Answer 1

Sem mais informações, você não pode fazer nada melhor do que $O(n^2)$ consultas para $f$, onde $n=|X|+|Y|$.Existe um argumento adversário simples.

Imagine que você tem um algoritmo que usa $o(n^2)$ consultas.Considere executá-lo em um set $X,Y$ escolhido para que $f(x,y)=0$ para todos $x \em X, y \em Y$.Se o algoritmo estiver correto, o algoritmo deverá retornar F nesta entrada.Como o algoritmo é executado em $o(n^2)$ tempo, deve existir algum par de elementos $x_0,y_0$ isso nunca foi questionado.Agora execute o algoritmo em um par de conjuntos $X,Y$ escolhido para que $f(x_0,y_0)=1$ mas $f(x,y)=0$ para todos os outros pares $x,y$.Nós vemos que $f$ sempre retorna 0 durante esta execução também, portanto esta execução deve seguir exatamente o mesmo caminho da primeira execução e, portanto, também deve retornar F nesta entrada.No entanto, retornar F nesta entrada está incorreto.Portanto, não existe um algoritmo que leve $o(n^2)$ tempo e está sempre correto.