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

Question

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

证明一个问题 X 是 NP:

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

显示问题 X 是 NP-Complete：

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，所以基本上你证明 NPC 的步骤 (3) 是多余的。

---

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

显示X是NP:

1. 证明 X 可以在多项式时间内确定地验证（或者 X 可以使用 NTM 求解）

显示X是NP-Hard:

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

或

2. 证明对于NP中的任何问题L，L≤p X（这实际上只做一次，对于SAT，并且是NP-Hard的定义）。

显示问题 X 是 NP-Complete:

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