假设这两个集合作为输入:
- 一组U作为universe
- 还有一组 S 包含 U 的一些子集。
S 的成员分配有随机 标志 0 或 1。对于 S 的每个成员，标志 1 的概率是 < em>p 并且标志 0 是 (1-p)。
所需的输出是:'Union of flag 1 subsets in S = U'
尽管考虑 S 中标志 1 子集的所有可能组合是导致输出的简单算法，但这种蛮力方法的运行时间显然是指数级的。
是否有任何多项式时间算法可以得出精确或近似的输出？或者我们可以将问题简化为任何著名的问题，例如 set-cover？
最佳答案
得到一个确切的答案是#P-hard(计算 NP 的模拟，因此至少同样困难)，因为这个问题概括了单调的 2-CNF-SAT，它被称为#P-hard(威尔士，多米尼克； Gale, Amy (2001)，“计数问题的复杂性”，复杂性方面:算法、复杂性和计算代数的迷你类(class):数学研讨会，凯库拉，2000 年 1 月 7-15 日，第 115 页，定理 57.)。归约是将U设置为子句标识符的集合，并让S中的每个子集成为某个变量出现的子句集合。编辑:为每个集合设置 p = 1/2，natch。
关于algorithm - 计算一组被随机子集覆盖的概率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52579747/