algorithm - 计算一组被随机子集覆盖的概率

Question

假设这两组作为输入给出：

• 一集U为宇宙
• 一组S包含U的一些子集。

S的成员分配有随机标志 0 或 1。对于S的每个成员，标志 1 的概率是p并且标志 0 是(1-p)。

所需的输出是：“ S = U中标志 1 子集的联合”的概率

尽管考虑到S中标志 1 子集的所有可能组合是导致输出的简单算法，但这种蛮力方法的运行时间显然是指数级的。

是否有任何多项式时间算法可以导致精确或近似输出？还是我们可以将问题简化为任何著名的问题，例如 set-cover？

标签： algorithmset

Answer 1

得到一个准确的答案是#P-hard（计算 NP 的类似物，因此至少一样难），因为这个问题概括了单调 2-CNF-SAT，它被称为 #P-hard（威尔士，多米尼克；盖尔，艾米(2001)，“计数问题的复杂性”，复杂性的方面：算法、复杂性和计算代数的迷你课程：数学研讨会，Kaikoura，2000 年 1 月 7 日至 15 日，第 115 页，定理 57。）。简化是将 U 设置为子句标识符集，并让 S 中的每个子集成为某些变量出现的子句集。编辑：为每组设置 p = 1/2，natch。