展示NP、NP完备性或NP难度

Question

我的理解关于三种问题类型是正确的吗？

为了证明问题X属于NP：

1. 展示X可以在多项式时间内被确定性地验证（或者X可以使用非确定性图灵机求解）。

为了证明问题X属于NP-完全：

1. 展示X可以在多项式时间内被确定性地验证（或者X可以使用非确定性图灵机求解）。
2. 展示存在已知的NP-完全问题L，使得L可以约化到X。
3. 展示存在已知的NP-完全问题L，使得X可以约化到L（这一步是否必要？若必要，这是什么区别了纯NP-难问题和NP-完全问题？）。

为了证明问题X属于NP-难：

1. 展示存在已知的NP-完全问题L，使得L可以约化到X。

- user

Answer 1

你已经接近正确答案了。

为了证明问题X是NP难的，你不需要展示存在一个NPC问题L满足X≤p L。

实际上，这一点已经得到保证。因为你已经证明了问题X在NP中（通过步骤1），并且你知道问题L是NP完全的。按照NP完全的定义，这意味着存在一个多项式时间可约化从NP中的所有问题到问题L，包括从问题X到L的可约化。因此，你在证明NPC时第3步其实是多余的。

更简单优雅的证明方法如下：

要证明问题X在NP中：

1. 展示问题X可以在多项式时间内被确定性地验证（或者说问题X可以使用NTM求解）。

要证明问题X是NP难的：

1. 展示对于一个已知的NP难问题L，L≤p X。

或者：

2. 展示对于NP中的任何问题L，L≤p X（实际上只需要对SAT证明一次，这就是NP难的定义）。

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

1. 展示问题X是NP难的。

2. 展示问题X在NP中。

- amit