algorithm - Np 完整性 - 需要对减少进行一些澄清

Question

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

现在假设我有 L<=L'。减少是从 L 到 L' 还是我也可以反过来做？即我可以证明如果 L 可以使用 L' 来解决，那么 L' 是 NP 完全的吗？

我对此感到很困惑。

例如。为了从火腿循环减少到火腿路径，我们采用了倒退的方式。

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

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

Answer 1

为了证明语言 L 是 NP 完全的，你实际上需要证明两件事，L 在 NP 中，L 是 NP-hard。通常，证明 L 在 NP 中很容易，但不要忘记这样做。

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

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

我在评论你关于哈密顿循环的问题时给了你一个提示。你读过提示并考虑过吗？如果是这样，请回答该问题。