포셋의 하위 집합 간의 분리 여부 확인

Question

포셋이 있다면 $(P, \le)$ 그리고 두 세트 $X \하위 기술 P$ 그리고 $Y \하위 기술 P$, 그리고 우리에겐 방법이 있어요 $f :P^2 \에서 2$로 효율적으로 계산하기 위해 $(x, y) \in P^2$ 존재하는지 여부 $z \in P$ 그렇게 $(x \le z) \웨지(y \le z)$, 우리는 돌아가고 싶습니다 $\mathbf{T}$ 쌍이 존재하는 경우 $(x, y) \in X imes 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 \in X, y \in 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)$ 시간은 항상 정확합니다.