定理证明过程的复杂度（Stephen A .Cook）定理1证明的解析

     The Complexity of Theorem-Proving Procedures这篇论文最难理解的部分就是定理1证明的过程，现在网络上中文材料并没有这方面的解析，这里给出详细解析，希望对这篇复杂度原始论文解读有个帮助，如有不对，希望指正。

定理1原话：

翻译过来就是，

定理1：如果字串集S被NDTM在多项式内接收，那么S多项式规约到DNF重言式。

注释：

所谓DNF（Disjunctive Normal Form）就是析取范式( A 1 ∨ A 2 ) ∧ ( A 3 ∨ A 4 )。与之相对的是CNF（Conjunctive Normal Form)合取范式 ( A 1 ∧ A 2 ) ∨ ( A 3 ∧ A 4 )。 他们可以用德摩根律取反转化。

证明过程:

为了便于理解分为两个部分，

第一部分是证明的整个思路，第二部分是DNF的构造过程。

1）证明思路

定理的证明：

    假设一个非确定性图灵机M能够在多项式时间Q（n）内接收字串集S。

给定一个输入w， 我们将构造一个CNF格式的公式A（w），如果M能够接收w（注：这里的意思是M的最终以accept状态停下）。这样~A（w）可以容易的放到DNF中(用德摩根律)，（注解：上面的论文显示可能是打印软件有误，把前面的取非操作掉了）。当且仅当w不在集合S中时，~A（w）是逻辑值始终为真的申明语句（英文就是tautology）。既然整个构造过程在多项式时间范围内（以w的长度|w|的多项式时间限度），定理得证。

2）DNF构造过程

2.1 图灵机与一些符号的约定

    我们可以假定图灵机M仅仅有一个带子，长度上从左到右是无限制的，但有一个起始的最左格子。我们可以给这些格子从左到右依次排序1，2，3，......。再假定一个S集中的一个固定输入w，其长度为n。那么就有一个M的计算过程，能够让M在T=Q（n）多项式步骤内停下，M状态机的状态是接收。那么公式A（w）参照这个计算过程，将根据以下符号中构建。

首先，假定M的带子的字母集合是{，，，，}，状态集是{q1,,,,,,qs}。注意到计算是在多项式时间T=Q（n）内完成的，因此不会有超过T的格子被扫描。

符号约定：

: 当格子s 在步骤t时包含字符时，该符号为真

：当在步骤t时，机器M在状态时，该符号为真

：当在时间t，格子s被带子读头扫描时，该符号为真

公式A（w） = B^C^D^E^F^G^H^I

具体的各范式构造如下，

2.2 A（w）的构造过程

B，设定每一步仅有一个格子被扫描；

B= B1^B2^B3...^BT

其中在每一步t的Bt是当且仅当一个格子被扫描。

前半部分构造表示至少一个被扫描，后半部分表示不可能同时有两个格子被扫描。

C， 设定在时间（步骤）t时，格子s中仅有一个符号；

D，设定每一步t，图灵机仅有一个状态s；

E，设定初始条件满足

这里w= q0是初始状态， 是空字符.

F,G,H 论断保障每一步，P， Q， S能够正确地更新。

最后I，设定机器在某个时候到达接收Accepting状态。

 通过上述构造，可以直接验证A（w）就是我们需要的范式。