algorithm - 如何有效地计算小尺寸的条件产品？

Question

这可能更像是一个数学问题而不是编程问题，但我已经考虑了一段时间并且很难弄清楚这是否是一个可解决的问题。

我有以下内容:

• 集合 A、B 来自一些符号集
• bool 函数 F : A × B → {0,1}

我想构造集合 C = {(x,y) : x ∈ A, y ∈ B, 其中 F(x,y) = 1}。

(对于任何一对，F 都可以在 O(1) 中计算)

到目前为止，如果 F 是常数时间，则此计算基本上只包含通过函数 F 在 A × B 上的过滤器，运行时间为 O(|A| × |B|)。

但是，我知道 C 的一个属性，我觉得它可以帮助我......

我知道|C| << |一个| |B|，事实上我很确定|C|关于|A|。我觉得有一些方法可以利用它(我最近被介绍了概率算法，我觉得它可以提供帮助，但我绝对不确定)。

我认为需要一些形式的辅助结构来解决这个问题，这本身应该不会有太大问题，只要结构只是 A 大小的多项式(计算幂集可能有点多，A 可能有点大)。

这也感觉像是已被证明具有某种下限复杂性的东西，但我真的没有学术知识来证明它。

任何关于我应该查看哪些域的指导和提示都将不胜感激。

到目前为止我想到了什么:

• 这看起来很像 SAT issue但我对那些事情几乎一无所知

• 这个问题与集合判别问题(至少……计算两个集合之间的差异)有点同构。但是，我无法以这种形式找到关于该主题的任何研究(只得到很多“迭代 A，迭代 B”类型的答案)。

Answer 1

在您提出问题的措辞中，唯一正确的解决方案是按照您的建议对 A 和 B 以及过滤器进行双重迭代。那是因为你已经陈述了关于“构造集合 C”的问题，它缺少其他信息，通常意味着枚举集合 C。唯一的方法就是做到这一点并获得 C 的精确枚举，至少根据所提供的信息，是在 A × B 中的每个元素上计算 F。

以另一种方式解释这个问题，如果你有一个特征函数，你可以说你有一个 C 的定义，但那只是 F。所以我假设这不是你的意思。

关键似乎是您需要阐明 F 的相关属性，因为这是 C 枚举的算法 Hook 。我的意思是您应该提出一个关于 F 的公理，让您可以通过一些捷径直接过滤。这可能意味着，例如，存在一些允许更短算法的辅助函数 G。假设有这样一个 G，枚举算法将评估 F 和 G，而不是单独评估 F。