algorithm - 子集推理 NP 完全？

Question

考虑以下问题:

有N个硬币，编号为1到N。

你看不到它们，但是给出了关于它们的 M 个事实，形式如下:

struct Fact
{
    set<int> positions
    int num_heads
}

positions 标识硬币的子集，num_heads 是该子集中正面硬币的数量。

鉴于这 M 个事实，您需要计算出可能出现的最大正面数量。

这个问题是NP完全的吗？如果有，减免是多少？如果不是，什么是多项式时间解？

例如:

N = 5
M = 3
fact1 = { {1, 2}, 1 } // Either coin 1 or coin 2 is a head
fact2 = { {4}, 0 } // Coin 4 is a tail
fact3 = { {2, 4, 5}, 2 } // Out of coins 2, 4 and 5, two are heads

符合事实的头最多的配置是:

T H H T H

所以答案是 3 个正面。

Answer 1

假设您有一个 3-SAT 问题。您可以将该问题中的每个 bool 变量 v 映射到两个硬币。称它们为“true(v)”和“false(v)”。这个想法是，如果 3-SAT 问题的解决方案中的 v 为真，则“true(v)”为正面；否则 'false(v)' 是正面。对于每个 v 你添加硬币约束

{true(v), false(v)} has 1 heads, and has 1 tails

在此之后，您可以翻译带有文字 l1、l2、l3 的 3-SAT 子句

l1 or l2 or l3

到硬币约束

{t/f(l1), t/f(l2), t/f(l3)} has at least 1 heads

其中 t/f(l1) 是 'true(l1)' 或 'false(l1)' 取决于 l1 在子句中是正数(未取反)还是负数(取反)。我们只需要证明“至少 1 个正面”可以在硬币问题中实现，因为“至少 1 个正面”不能直接表达。这可以通过以下设备完成。假设 C1、C2、C3 是三个硬币，我们要为其声明约束“至少其中一个是正面”。创建另外三个硬币 X1、X2、X3 并放入约束

{X1, X2, X3, C1, C2, C3} has 4 heads

但 X1、X2、X3 没有其他约束。仅当 C1、C2、C3 中至少有一个是正面时，才满足此约束；硬币 X1..3 可用于提供剩余的所需头部。

请注意，这种减少根本没有使用问题的“最大磁头数”方面；如果 3-SAT 公式不可满足，则显然根本不可能为表示 bool 变量的硬币选择正面/反面状态。

这是从 3-SAT 到您的硬币问题的多项式约简，表明它是 NP-hard。要证明它是 NP 完全的，只需观察您的硬币问题的解决方案可以在多项式时间 QED 中检查。