gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:38:14 27 4
gpt4 key购买 nike

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

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

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

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

预先感谢您的回答。

最佳答案

(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=SATA是某个问题P,令M_A是求解A的多项式时间算法。

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

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

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

关于algorithm - NP 中的语言(问题)和 P 中的语言(问题)之间的多项式时间减少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24237763/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com