子集推断NP完全？

有编号为1到N

你不能看到他们ň硬币，但鉴于有关它们的形式的M个事实：

struct Fact 
{ 
    set<int> positions 
    int num_heads 
}

positions识别硬币的一个子集，并且num_heads是该子集中硬币的头数。

鉴于这些M事实，您需要计算出可能的最大头数。

这个问题NP-complete？如果是，那么减少是多少？如果不是，什么是多项式时间解决方案？

例如：

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头。

来源

2012-05-17 Andrew Tomazos

也许我对你在这里提出的问题没有足够的了解，但你确定 - 作为第一件事 - 这个问题甚至是可以决定的吗？ –

@ B.VB。这当然是可以决定的：一个简单的指数算法是枚举所有2^N个可能的赋值，并根据M个事实来检查它们，用最多的头部跟踪解决方案。这是时间O（N M 2^N）。 – Dougal

SAT似乎应该有所减少，但我无法完成它的工作。不过，我有80％的确实是NP。 – Dougal

假设你有3-SAT问题。您可以将该问题中的每个布尔变量v映射到两个硬币。称他们为'真（v）'和'假（v）'。这个想法是，如果v在3-SAT问题的解决方案中是真实的，那么'真（v）'是正确的;否则“假（五）”是头。对于每一个v您添加硬币约束

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

在此之后，你可以用文字L1，L2，L3

l1 or l2 or l3

一个3-SAT条款翻译成硬币约束

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

其中t/f（l1）可以是'真（l1）'或'假（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-hard。为了显示它是NP完全的，只需观察一下，可以在多项式时间QED中检查您的硬币问题的解决方案。

来源

2012-05-17 15:46:19

嗯，看起来我减少了硬币问题的另一个变种...... :)你不能在你的问题中有一个“至少有一个头”的限制。嗯 –

好的问题解决了减少。 –

您可以使用[三分之一3SAT]（http://en.wikipedia.org/wiki/One-in-three_3SAT）跳过X1，X2，X3的窍门。 – sdcvvc

One-in-three 3SAT简单地降低到您的问题的决定版本（是否存在配置？），这在NP中是平凡的。最大化版本是NP-硬（但不完整，因为它不是一个决策问题），即使是承诺版本，其中必须有一个令人满意的配置：添加到决策减少输出一个额外的硬币出现在所有的造成一个坏的额外的解决方案，那个硬币是头，其他的都是尾巴。

来源

2012-05-17 16:06:23 Chris

完美匹配可以直接减少此问题 - 将边缘表示为硬币，因为图形中的每个顶点都会创建一个事实，规定偶然边缘中的一个是正面。只有当硬币有解决方案时，原始图形中的完美匹配才存在。

来源

2012-05-18 07:08:29

子集推断NP完全？

回答

相关问题