这可能更像是一个数学问题而不是编程问题，但我一直在考虑这个问题并且很难弄清楚这是否是一个可解决的问题。
我有以下内容：
- 集合A，B源自某些符号集
- 布尔函数F : A × B → {0,1}
我希望构造集合 C = {(x,y) : x ∈ A, y ∈ B, F(x,y) = 1}。
（对于任何对，F 都可以在 O(1) 中计算出来）
现在到现在为止，这个计算基本上只包括通过函数 F 对 A × B 进行过滤，如果 F 是常数时间，则运行在 O(|A| × |B|) 中。
但是，我知道 C 的一个属性，我觉得可以帮助我...
我知道|C| << |一个| |B| , 事实上我很确定|C| 大约是 |A| . 我觉得有一些方法可以利用这一点（我最近被介绍给概率算法，我觉得这可能会有所帮助，但我绝对不确定）。
我想需要一些形式的辅助结构来解决这个问题，这本身不应该有太大问题，只要结构只是A大小的多项式（计算幂集可能有点多，A 可以有点大）。
这也感觉像是已被证明具有某种下限复杂性的东西，但我并没有真正的学术知识来证明这一点。
任何关于我应该关注哪些领域的指导和提示将不胜感激。
到目前为止我的想法是：
这看起来很像SAT 问题，但我对这些事情几乎一无所知
这个问题感觉与集合判别问题略有同构（至少......计算两个集合之间的差异）。但是，我无法以这种形式找到有关该主题的任何研究（仅获得很多“迭代 A，迭代 B”类型的答案）。