子集推理NP-complete？

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 问题。您可以将该问题中的每个布尔变量 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 公式不可满足，那么显然根本不可能为代表布尔变量的硬币选择正面/反面状态。

这是从 3-SAT 到硬币问题的多项式约简，表明它是 NP 困难的。为了证明它是 NP 完全的，只需观察硬币问题的解决方案可以在多项式时间内（QED）进行检查。