设计与分析库克定理

斯蒂芬·库克在他的论文《定理证明程序的复杂性》中提出了四个定理。这些定理如下所述。我们确实了解本章中使用了许多未知术语，但我们没有足够的空间来详细讨论所有内容。

以下是斯蒂芬·库克的四个定理 -

定理-1

如果一组S字符串在多项式时间内被某个非确定性图灵机接受，则S可 P 约简为 {DNF 同义反复}。

定理2

以下集合可以成对地彼此 P 约简（因此每个集合都具有相同的多项式难度）：{重言式}、{DNF 重言式}、D3、{子图对}。

定理3

  • 对于任何类型为Q的T Q (k)，$\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ 为无界的

  • 存在Q类型的T Q (k)，使得 $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$

定理4

如果字符串集合 S 在时间T(n) = 2 n内被非确定性机器接受，并且如果T Q (k)是类型Q的诚实（即实时可数）函数，则存在常数K，因此S可以在时间T Q (K8 n )内被确定性机器识别。

  • 首先，他强调了多项式时间可约性的重要性。这意味着，如果我们从一个问题到另一个问题的多项式时间减少，这确保了第二个问题的任何多项式时间算法都可以转换为第一个问题的相应多项式时间算法。

  • 其次，他将注意力集中在可以由非确定性计算机在多项式时间内解决的决策问题的 NP 类。大多数棘手的问题都属于这一类，NP。

  • 第三，他证明了 NP 中的一个特定问题具有以下性质，即 NP 中的所有其他问题都可以多项式约简到它。如果可满足性问题可以用多项式时间算法解决，那么NP中的每个问题也可以在多项式时间内解决。如果 NP 中的任何问题是棘手的，那么可满足性问题也必定是棘手的。因此，可满足性问题是NP中最难的问题。

  • 第四，库克提出，NP 中的其他问题可能与可满足性问题一样，都是 NP 中最难的成员。