algorithm - Np 完整性 - 需要一些关于减少的澄清

Question

我想要一些概念上的澄清。为了证明问题是 NP 完全的，我们使用归约。

现在假设我有 L<=L'。是从 L 减少到 L' 还是我也可以用相反的方式来减少？即我能否证明如果 L 可以使用 L' 求解，那么 L' 是 NP 完全的？？

我对此很困惑。

例如。对于从火腿循环到火腿路径的减少，我们采用向后的方式。

此外，我无法通过从 ham 循环减少来解决我必须证明“在至少有 k 条边的图中是否存在从 s 到 t 的路径”的问题。

请给我一个澄清，并指导我解决上述问题。谢谢

Answer 1

要证明语言 L 是 NP 完全的，您实际上需要证明两件事，L 在 NP 中并且 L 是 NP 难的。通常，证明 L 在 NP 中很容易，但不要忘记去做。

显示 L 是 NP-hard 的正常方法实际上是显示 L 的多项式时间决策器可以用于为已被证明是 NP 的语言 L' 构建多项式时间决策器-完成。

一定是这样的。有许多多项式时间可判定语言 L 的情况，可以从 NP 完全语言的多项式时间判定器构建多项式时间判定器。例如，考虑用两种颜色为图形着色的多项式时间可判定问题，以及 NP 完全一般图形着色问题。

我在对您关于哈密顿循环的问题的评论中给了您提示。您是否已阅读提示并考虑过？如果是，请在该问题中回复。