1

如果我有一个决策问题 A，并希望证明它是 NP 完全的。是否足以证明另一个 NP 完全问题多项式简化为 A，或者我必须证明另一个 NP 完全问题多项式转换为 A？

也就是说，我可以证明

procedure solve_SAT
...
call solve_A
call solve_A
call solve_A
...
end

还是我只限于一次使用solve_A，如图所示

procedure solve_SAT
input  = ...
result = call solve_A(input)
return result
end

我发现一些消息来源说前者，而其他消息来源说后者，这让我有点困惑。

4

3 回答 3

2

假设您有一个决策问题 A，并且您希望证明它是 NP-Complete，那么这样做的方法是，采用现有的 NP-Complete 问题并将其简化为 A。我这里所说的减少是多项式时间减少.

因此，假设您想证明 3-SAT 是 NP-Complete，那么您可以证明 SAT 问题的减少。

这里要注意的重要一点是减少必须是多时间的。是否多次调用solve_A() 并不重要。只要对solve_A() 进行多项式调用，就可以选择多次调用solve_A()。

为什么它有效？你可以用反证法来证明。假设你有一个 3SAT 的多时间算法。然后你也可以在多时间内解决 SAT 问题。由于多项式函数的多项式调用次数仍然是多项式。因此，除非 P=NP，否则这意味着 SAT 也可以使用新发现的 3SAT 多时间算法在多项式时间内求解。但是我们知道 SAT 是 NP-Complete，因此 3SAT 也必须是 NP-Complete。

简而言之，要显示 NP 完备性，需要做两件事。

证书的存在。从现有的 NP 完全问题减少。

于 2012-01-28T01:21:34.140 回答
1

如果您的solve_SAT 过程仅使用固定数量的solve_A 调用，那么A 的多项式时间算法将暗示SAT 的多项式时间算法。这不符合 SAT 的确切定义，但它意味着不存在 A 的多项式时间算法，除非 P = NP。

于 2011-09-13T19:54:54.647 回答
0

今天确定的 NP 完全性的定义是，为了显示 NP 完全性，需要从已知的 NP 完全问题到您的问题的多项式多一或 Karp 减少。这也称为多项式变换，对应于您的示例，您只能调用一次 solve_A 函数。

您的另一个示例，您可以调用 solve_A 多项式次数对应于图灵或库克减少。从 NP 完全问题到您的问题的图灵简化的存在证明了您的问题的 NP 难度，这被认为是与 NP 完全性不同的属性。

于 2012-01-27T05:20:53.060 回答