一个约简足以证明np完全吗，还是我需要一个变换

Question

如果我有一个决策问题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

我发现一些来源说是前者，而另一些来源说是后者，这让我有点困惑。

Answer 1

假设你有一个决策问题a，你希望证明它是np完全的，那么做的方法是，取一个现有的np完全问题并将其约简为a。我这里所说的缩减是指多项式时间的缩减。

假设你想证明3-SAT是np完全的，那么你可以展示SAT问题的简化。

这里需要注意的重要一点是，减少必须是多时间的。是否多次调用solve_A()并不重要。您可以选择多次调用solve_A()，只要您调用solve_A()的次数达到多项式。

为什么它工作?你可以用反证法来证明。假设你有一个3SAT的多时间算法。那么你也可以用多时间解SAT。因为对多项式函数的多项式次数调用仍然是多项式。因此，除非P=NP，否则这意味着SAT也可以使用新发现的3SAT的多时间算法在多项式时间内求解。但是我们知道SAT是np完全的，因此3SAT也一定是np完全的。

简而言之，要证明np完备性需要两个条件。

证书是否存在。一个现有np完全问题的约简。

Answer 2

如果您的solve_SAT程序只使用对solve_A的常数次调用，那么a的多项式时间算法将意味着SAT的多项式时间算法。这不符合SAT的确切定义，但它意味着除非p = NP，否则不存在a的多项式时间算法。

Answer 3

今天确定的np完备性的定义是，需要从已知的np完备问题到您的问题的多项式多一或Karp约简来显示np完备性。这也被称为多项式变换，对应于你只调用一次solve_A函数的例子。

你的另一个例子，你可以调用solve_A一个多项式次数对应于图灵或库克约简。从np完全问题到你的问题的图灵约简的存在性证明了你的问题的np硬度，这被认为是一个不同于np完全的性质。