减少足以证明 NP 完全还是我需要转换？
如果我有一个决策问题 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
，我发现一些消息来源说前者，而其他消息来源说后者，这让我有点困惑。
If I have a decision problem A, and wish to show that it is NP-complete. Is it enough to prove that another NP-complete problem polynomially reduces to A, or must I show that another NP-complete problem polynomially transforms to A?
That is, can I show that
procedure solve_SAT
...
call solve_A
call solve_A
call solve_A
...
end
or am I only limited to a single use of solve_A, as shown
procedure solve_SAT
input = ...
result = call solve_A(input)
return result
end
I find some sources say the former while other sources say the latter, and it is a bit confusing to me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
假设您有一个决策问题 A，并且您希望证明它是 NP 完全问题，那么方法是，采用现有的 NP 完全问题并将其简化为 A。
我这里所说的减少是指多项式时间减少。
因此，假设您想证明 3-SAT 是 NP 完全的，那么您可以证明 SAT 问题的简化。
这里需要注意的是，减少必须是多时间的。是否多次调用solve_A()并不重要。您可以选择多次调用solve_A()，只要对solve_A() 进行多项式调用即可。
为什么它有效？可以用反证法来证明。
假设您有 3SAT 的多时间算法。然后你也可以在复试时间内解决 SAT 问题。由于调用多项式函数的多项式次数仍然是多项式。
因此，除非 P=NP，否则这意味着 SAT 也可以使用新发现的 3SAT 多项式时间算法在多项式时间内求解。但我们知道 SAT 是 NP-Complete，因此 3SAT 也一定是 NP-Complete。
简而言之，要证明 NP 完备性需要满足两件事。
证书的存在。
现有 NP 完全问题的简化。
Suppose you have a decision problem A and you wish to prove that it is NP-Complete then the way to do it is, take an existing NP-Complete problem and reduce it to A.
What I mean by reduction here is a polynomial time reduction.
So suppose you wanted to show that 3-SAT is NP-Complete then you can show a reduction from the SAT problem.
The important thing to note here is that the reduction must be poly-time. It doesn't matter whether you call solve_A() multiple times. You can choose to call solve_A() multiple times as long as you make a polynomial number of calls to solve_A().
Why does it work? You can prove it by contradiction.
Suppose you had a poly-time algorithm for 3SAT. Then you could solve SAT also in poly-time. Since a polynomial number of calls to a polynomial function is still polynomial.
So unless P=NP, this would imply that SAT can also be solved in polynomial time using the newly discovered poly-time algorithm for 3SAT. But we know that SAT is NP-Complete, hence 3SAT must also be NP-Complete.
In short, to show NP-Completeness two things are required.
Existence of a certificate.
A reduction from an existing NP-Complete problem.
如果您的solve_SAT 过程仅使用恒定数量的solve_A 调用，则A 的多项式时间算法将意味着SAT 的多项式时间算法。这不符合 SAT 的确切定义，但它意味着除非 P = NP，否则不存在 A 的多项式时间算法。
If your procedure for solve_SAT uses only a constant number of calls to solve_A, then a polynomial-time algorithm for A would imply a polynomial time algorithm for SAT. This doesn't meet the exact definition of SAT, but it would imply that no polynomial-time algorithm for A exists unless P = NP.
今天确定的 NP 完整性的定义是，需要从已知的 NP 完全问题到您的问题进行多项式多一或卡普约简来显示 NP 完整性。这也称为多项式变换，对应于您只能调用一次solve_A函数的示例。
您的另一个示例，您可以调用solve_A多项式次数对应于图灵或库克简化。从 NP 完全问题到您的问题的图灵约简的存在证明了您的问题的 NP 难度，这被认为是与 NP 完全性不同的属性。
The definition for NP-completeness settled upon today is that a polynomial many-one or Karp reduction from a known NP-complete problem to your problem is needed to show NP-completeness. This is also known as a polynomial transformation and corresponds to your example where you only get to call your solve_A function once.
Your other example, where you can call solve_A a polynomial number of times corresponds to the Turing or Cook reduction. The existence of a Turing reduction from an NP-complete problem to your problem is proof of the NP-hardness of your problem, which is thought to be a different property than NP-completeness.