التحقق من الانفصال بين مجموعات فرعية من الوضع

Question

إذا كان هناك وضعية $(P, \le)$ ومجموعتين $X \subseteq P$ و $Y \subseteq P$, ، ولدينا طريقة $و :ف ^ 2 \ إلى 2 دولار لحساب بكفاءة لأي $(x, y) \في P^2$ ما إذا كان هناك أ $z \في P$ مثل ذلك $(x \le z) \wedge (y \le z)$, ، نريد العودة $\mathbf{T}$ إذا كان هناك زوج $(x, y) \في X \مرات Y$ مثل ذلك $f(x, y) = 1$ و $\mathbf{F}$ وبخلاف ذلك، باستخدام أقل عدد ممكن من المكالمات إلى $و$ و $\ لو$.

Answer 1

بدون مزيد من المعلومات، لا يمكنك أن تفعل أي شيء أفضل من $O(ن^2)$ الاستفسارات ل $و$, ، أين $n=|X|+|Y|$.هناك حجة خصم بسيطة.

تخيل أن لديك خوارزمية تستخدم $س(ن^2)$ الاستعلامات.النظر في تشغيله على مجموعة $س، ص$ اختار ذلك $f(x,y)=0$ للجميع $x \في X، y \في Y$.إذا كانت الخوارزمية صحيحة، فيجب أن ترجع الخوارزمية F على هذا الإدخال.منذ أن تم تشغيل الخوارزمية $س(ن^2)$ الوقت، يجب أن يكون هناك بعض العناصر $x_0,y_0$ لم يتم الاستفسار عن ذلك أبدًا.الآن قم بتشغيل الخوارزمية على زوج من المجموعات $س، ص$ اختار ذلك $f(x_0,y_0)=1$ لكن $f(x,y)=0$ لجميع الأزواج الأخرى $x,y$.نحن نرى ذلك $و$ يُرجع دائمًا 0 أثناء هذا التنفيذ أيضًا، لذلك يجب أن يتبع هذا التنفيذ نفس مسار التنفيذ الأول تمامًا، وبالتالي يجب أيضًا إرجاع F على هذا الإدخال.ومع ذلك، فإن إرجاع F على هذا الإدخال غير صحيح.لذلك، لا توجد خوارزمية تأخذ $س(ن^2)$ الوقت ودائما على حق.