子集推断问题是否是NP完全问题？

Question

子集推断问题是否是NP完全问题？

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

- Andrew Tomazos

也许我对你在这里提出的问题没有想得够久或够深入，但是你确定作为第一步，这个问题是否可判定吗？ - Bill

2

@B.VB。这肯定是可决的：一个简单的指数算法是枚举所有2^N个可能的赋值，并将它们与M个事实进行检查，跟踪具有最多头的解决方案。这需要的时间是 O(N M 2^N)。 - Danica

1

似乎用SAT应该有一个简化，但是我无法使其正常工作。虽然我有80％的把握它在NP中。 - Danica

请看我的答案，将3-SAT问题简化为硬币问题，证明它是NP难的。由于多项式检查可用于验证解决方案，因此NP完全性得以证明。 - Antti Huima

3个回答

1

One-in-three 3SAT问题可以简单地归约到你的问题的决策版本（是否存在任何一种配置），这个版本显然属于NP。最大化版本是NP-难的（但不完全，因为它不是一个决策问题），即使在必须有满足条件的配置的承诺版本中也是如此：将决策归约的输出添加一个额外的硬币，该硬币出现在所有子集中，创建一个坏的、额外的解决方案，其中该硬币为正面而其他硬币为反面。

- Chris

0

完美匹配问题可以直接转化为这个问题 - 将边表示为硬币，在图中的每个顶点上创建一个事实，规定恰好有一条关联边是正面朝上。原始图中存在完美匹配当且仅当硬币问题有解。

- Rafał Dowgird

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Antti Huima · Accepted Answer

假设您有一个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)是指在子句中，如果l1为正（非否定），则为“true(l1)”，否则为“false(l1)”。我们只需要展示可以将“至少有一个正面”在硬币问题中实现，因为“至少有一个正面”无法直接表达。可以使用以下设备来实现：让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。