5

考虑以下问题：

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

4

3 回答 3

2

假设你有一个 3-SAT 问题。您可以将该问题中的每个布尔变量 v 映射到两个硬币。称它们为“真（v）”和“假（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。

于 2012-05-17T15:46:19.737 回答
1

三分之一的 3SAT微不足道地简化为问题的决策版本（是否存在配置？），这在 NP 中微不足道。最大化版本是 NP难的（但不完整，因为它不是一个决策问题），即使是承诺版本也必须有一个令人满意的配置：在决策缩减的输出中添加一个出现在所有子集中的额外硬币，创建一个糟糕的额外解决方案，其中硬币是正面，所有其他都是反面。

于 2012-05-17T16:06:23.243 回答
0

完美匹配可以直接减少这个问题 - 将边表示为硬币，因为图中的每个顶点都会创建一个事实，规定恰好有一个附带边是正面。当且仅当硬币有解时，原始图中存在完美匹配。

于 2012-05-18T07:08:29.227 回答