NP猜想（一） (4-3)

ACM Sympc'm

斯蒂芬·A·库克

多伦多大学

1471年5月

森马里

对某些递归的字符串集合，这个字母表，我们感兴趣的问题是找到，一个好的下界，它可能的识别时间。我们在这里没有提供这样的下界，但是定理1将给出证明(重言式！)是一个难以识别的集合，因为许多明显困难的问题可以简化为确定τ-logy。通过约简，我们的意思是，粗略地说，如果同义反复可以立即决定(通过“oraclc”)，那么这些，问题可以在多项式时间内决定。为了使这个概念更加精确，我们引入了查询机器，它类似于[1]中的图灵机。

证明了任何由多项式时间·有界不定图灵机求解的识别问题都可以“简化”为确定给定的命题公式是否为重言式的问题。“约化”的意思是，粗略地说，第一个问题可以在多项式时间内确定性地解决，前提是有一个预言器可用于解决第二个问题。从可约性的概念出发，定义了多项式的难易度，并证明了判定重言式的问题与判定两个给定的图中的第一个是否与第二个子图同构的问题具有相同的多项式度。讨论了其它例子，介绍并讨论了一种降低谓词演算证明过程复杂度的方法。

guery机器是一种多磁带图灵机，它有一种被称为guery磁带的可分辨磁带，以及三种被称为查询状态、是状态和否状态的可分辨状态。

I4a

（一）什么是NPC（NP-Complete）问题？

如果用最通俗的话来介绍，NPC问题就是NP问题中最难的那一类问题，或者说任何NP类问题的难度都小于等于NPC类问题。那么怎么定义这个“最难”呢？

如果说问题1可以在多项式时间复杂度内转换为问题2，我们就说问题2的难度大于等于问题1 。

更严格一点的描述为：设有两个问题 L₁ 和 L₂ ， S₁ 和 S₂ 分别为 L₁ 和 L₂ 的所有待验证的解的集合（就是穷举法中全部需要判断的解的集合）， l₁ 和 l₂ 分别为 L₁ 和 L₂ 的解的集合，如果存在一个多项式时间复杂度的算法能够完成的映射 f：S₁ → S₂ ，使得当且仅当 i∈l₁ 时， f(i)∈l₂ ，我们就说问题 L₁ 可以在多项式时间复杂度内转换为问题 L₂ ，称为问题 L₁ 可以归约为问题 L₂ ，记作 L₁ ∝ L₂ 。

这种归约关系显然是可传递的，也就是说，如果 L₁ ∝ L₂ 且 L₂ ∝ L₃ ，那么 L₁ ∝ L₃ 。

这种情况下，问题2如果能够在多项式时间复杂度内得到解决，或者说如果问题2是一个“P类问题”，那么问题1显然也会是一个“P类问题”。这是比较显然的，简略证明如下：

按照前面的定义，L₁ ∝ L₂ ，并设问题 L₁ 和 L₂ 的最大规模为n，映射f可以在 P₁(n) 的步骤内完成。如果 L₂ 可以在 P₂(n) 步骤内得到解决，即在 P₂(n) 步骤内可以得到 l₂ ，那么我们再用 n · P₁(n) 的步骤得到 f(S₁) ，对于使 f(S₁)中元素 属于 l₂ 的 S₁ 的子集即构成 l₁ 。因此，可以用 n · P₁(n)＋P₂(n) 的时间复杂度得到 l₁ ，也就是得到 L₁ 的解集。

由于 P₁(n) 和 P₂(n) 都是多项式，因此n · P₁(n)＋P₂(n) 也是一个多项式，即问题 L₁ 也可以通过多项式时间复杂度求解，从而 L₁ 也是一个“P类问题”。

既然我们说NPC问题是所有NP类问题中最难的那种，那么按照上述定义，也就意味着如果一个问题是NPC问题需要满足两个条件：一是它首先要是一个NP类问题；二是任何其它NP类问题都可以归约到这个问题。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。