Проверка несвязанности между подмножествами набора

Question

Если есть группа $(P, \le)$ и два комплекта $X \ подмножество P$ и $Y \ подмножество P$, и у нас есть способ $f :P^2 \к 2$ эффективно вычислять для любого $(x, y) \в P^2$ существует ли $z \в P$ такой , что $(x \ le z) \клин (y \le z)$, мы хотим вернуться $\mathbf{T}$ если существует пара $(x, y) \в X \ умноженных на Y$ такой , что $f(x, y) = 1$ и $\mathbf{F}$ в противном случае, используя как можно меньшее количество вызовов для $f$ и $\le$.

Answer 1

Без дополнительной информации вы не сможете добиться ничего лучшего, чем $O(n^2)$ запросы к $f$, где $n=|X|+|Y|$.Есть простой аргумент противника.

Представьте, что у вас есть алгоритм, который использует $o(n^2)$ запросы.Подумайте о том, чтобы запустить его на съемочной площадке $X,Y$ выбран таким образом, чтобы $f(x,y)=0$ для всех $x \в X, y \в Y$.Если алгоритм верен, алгоритм должен вернуть F для этого ввода.Поскольку алгоритм выполняется в $o(n^2)$ раз, должна существовать какая-то пара элементов $x_0,y_0$ это никогда не подвергалось сомнению.Теперь запустите алгоритм на паре наборов $X,Y$ выбран таким образом, чтобы $f(x_0,y_0)=1$ но $f(x,y)=0$ для всех остальных пар $x,y$.Мы видим, что $f$ также всегда возвращает 0 во время этого выполнения, поэтому это выполнение должно следовать точно по тому же пути, что и первое выполнение, и, следовательно, также должно возвращать F на этом входе.Однако возврат F для этого ввода неверен.Следовательно, не существует алгоритма, который принимает $o(n^2)$ вовремя и всегда корректно.