NP-Complete证明减少（方向）？

Question

为什么你不得不减少的NP完全的算法，你要证明该算法是NP完全问题，而不是反之亦然？我觉得解释很简单 - 我已经在网上搜索了它，但没有成功 - 但我的想法并没有很好地包围它。

谢谢:)

Answer 1

因为如果你能问题的减少问题B，那么问题B不能低于A.任何容易，毕竟，你现在有解决问题的一个实例的新方式！把它变成问题B的一个实例并解决这个问题。如果B很容易，那么在这个过程中A也很容易。

，只有当翻译问题实例的过程本身并不难，这就是为什么你还必须证明工作。如果翻译被允许很难，它可以解决这个问题，让B变得微不足道。

而且本身只证明题B NP难的，为了证明问题B是NP完全问题也必须证明它在NP（通常是更容易比减少）。

其他的方式只是表明你的问题并不比NP完全问题，这也不是完全没用的困难，但一般不太感兴趣。例如，你就可以解决问题“是存在的整数x使得x*3=9”与使用二进制乘法和编码的电路，作为一个实例SAT，但问题是容易得多一个SAT解算器。