algorithm - NP 中的语言(问题)和 P 中的语言(问题)之间的多项式时间减少

Question

你好，我很难理解 P、NP 和多项式时间缩减的主题。我试过在网上搜索它并问过我的一些 friend ，但我没有得到任何好的答案。

我想问一个关于这个话题的一般性问题:

设 A,B 为 P 中的语言(或问题集)设 C,D 为 NP 语言以下哪些必然为真(可能不止 1 个)

1. 存在从 A 到 B 的多项式时间缩减
2. 存在从 A 到 C 的多项式时间缩减
3. 存在从 C 到 A 的多项式时间缩减
4. 存在从 C 到 D 的多项式时间缩减

预先感谢您的回答。

Answer 1

(1) 为真(B={} 和 B={all words} 除外)，具有以下多项式约简:

Let w_t be some word such that B(w_t)=true, and w_f be some word such that B(w_f)=false.
Given a word w: Run A(w). If A(w)=true, return w_t - otherwise, return w_f

以上是多项式归约，因为所有运算都是多项式的，当且仅当 A(w)=true 时，归约的输出为 B(f(w))=true 。

(2) 再次为真，具有相同的缩减(同样，如果您可以假设有一个 w_t 和一个 w_f，如所描述的那样)。

(3) 这是错误的，假设 P!=NP。

假设存在这样的减少，让它成为 f:Sigma*->Sigma*。
检查问题C=SAT，A是某个问题P，令M_A是求解A的多项式时间算法。

我们将展示我们可以在多项式时间内解决 SAT(但由于我们假设 P!=NP，这是不可能的 - 矛盾，所以 f 不存在)。

给定 SAT w 的实例，运行 w'=f(w)。运行 M_A(w')，并回答相同的问题。
上面显然是多项式，它总是返回正确答案 - 根据多项式约简的定义 - f(w) 在 A 中当且仅当w 在 C 中。
因此-上述算法在多项式时间内解决了SAT-矛盾。

(4) 也是错误的，因为情况 (3) 包含在其中。