检查POSET子集之间的差异

Question

如果存在poset $（p，\ le）$ 和两个set $ x \ subseteq p $ 和 $ y \ subseteq p $ ，我们有一个方法 $ f：p ^ 2 \到2 $为了有效计算任何 $（x，y）\ in p ^ 2 $ 是否存在 $z \在p $ 这样 $（x \ le z）\ wedge（y \ le z）$ ，我们想要返回 $ \ mathbf {t} $ 如果存在一对 $（x，y）\ in x \ times y $ 其中 $ f（x，y）= 1 $ 和 $ \ mathbf {f} $ 否则，使用对 $ f $ 和 $ \ le $ 。

Answer 1

无需进一步的信息，您无法做得更好，而不是 $ o（n ^ 2）$ 查询到 $ f $ ，其中 $ n= | x | + | y | $ 。有一个简单的对手论证。

想象一下，您有一个使用 $ o（n ^ 2）$ 查询的算法。考虑在set $ x上运行它，所以选择 $ f（x，y）= 0 $ 对于所有 $ x \ in x，y \ in y $ 。如果算法正确，则算法必须在此输入上返回F.由于算法在 $ o（n ^ 2）$ 时间内，因此必须存在某些元素 $ x_0，y_0 $ 从未查询过。现在在一对SET中运行算法 $ x，y $ 所选的，所以 $ f（x_0，y_0）= 1 $ 但 $ f（x，y）= 0 $ 所有其他对 $ x，y $ < / span>。我们看到 $ f $ 在此执行期间始终返回0，因此此执行必须遵循与第一个执行完全相同的路径，因此还必须返回f上这个输入。但是，在此输入上返回F不正确。因此，没有算法需要 $ o（n ^ 2）$ 时间，始终是正确的。