algorithm - NP 完全证明缩减(方向)？

Question

为什么您必须将 NP 完全算法简化为您试图证明的算法是 NP 完全算法，而不是反之亦然？我觉得解释很简单——我已经在网上搜索过，但没有成功——但我的想法并没有很好地围绕它。

谢谢!:)

Answer 1

因为如果你可以将问题 A 简化为问题 B，那么问题 B 就不会比 A 更容易了。毕竟，你现在有了解决问题 A 实例的新方法:将其转化为问题 B 的实例并求解那。如果 B 很容易，那么通过该过程 A 也很容易。

只有在翻译问题实例的过程本身并不困难的情况下，这才有效，这就是为什么你也必须证明这一点。如果允许翻译困难，它可以解决问题，让B变得微不足道。

并且它本身只能证明问题 B NP-hard，为了证明问题 B 是 NP-完全的，您还必须证明它是 NP(这通常比归约更容易)。

反过来只是表明您的问题并不比 NP 完全难，这并非完全无用，但通常没那么有趣。例如，您可以使用 SAT 求解器解决问题“是否有一个整数 x 使得 x*3=9”，该求解器使用二进制乘法电路并将其编码为SAT 实例，但该问题要容易得多。