algorithm - 显示 NP、NP-完全性或 NP-硬度

Question

我对这三个类别的理解是否正确？

要证明问题 X 是 NP:

1. 表明 X 可以在多项式时间内确定性地得到验证(或者X 可以使用 NTM 解决)

要证明问题 X 是 NP 完全的:

1. 表明 X 可以在多项式时间内确定性地得到验证(或者X 可使用 NTM 求解)
2. 证明给定一个已知的 NP-C 问题 L，L ≤p X
3. 证明给定一个已知的 NP-C 问题 L，X ≤p L(这一步是必要的？如果是这样，这就是区分纯 NP-Hard 的原因吗？来自 NP-C 问题的问题？)

为了证明问题 X 是 NP-Hard:

1. 证明给定一个已知的 NP-C 问题 L，L ≤p X

Answer 1

你几乎明白了。

给定一个问题X，为了显示它是NPC，你不需要显示X ≤p L，对于一些NPC问题L.

事实上，这是有保证的，因为您已经表明 X 在 NP 中(在 1 中)，并且您知道 L 是 NP-Complete。根据 NP-Complete 的定义，这意味着从 NP 中的所有问题到 L(包括从 X)都有一个多项式时间减少，所以基本上你的步骤(3)证明NPC 是多余的。

---

一种更优雅的方式来显示证明每个属性需要做什么的陈述:

要显示 X 是 NP:

1. 表明 X 可以在多项式时间内确定性地得到验证(或者 X 可以使用 NTM 求解)

要显示 X 是 NP-Hard:

1. 证明给定一个已知的 NP-Hard 问题 L，L ≤p X

或

1. 证明对于 NP 中的任何问题 L，L ≤p X(对于 SAT，这实际上只完成一次，并且是 NP-Hard 的定义)。

要证明问题 X 是 NP 完全的:

1. 证明 X 是 NP-Hard
2. 显示 X 在 NP 中