计算机可解问题都是多项式时间

姜咏江

P/NP的问题使用一般程序方式求证，会进入复杂境界，因为程序执行的基础并不清楚。从计算机构造及运行方式理解，基础清晰，难度会极大降低。

1. 什么是计算机可解问题？

简单地说，就是一切可以通过计算机程序运行方式得到结果的问题。

程序不论多大，都是由有限个指令组成的。而能够解决问题的程序执行过程，尽管执行的指令数可以会远远超过程序写出来的指令数，但仍然是一个有限次过程，不然就得不到问题的结果。

2. 微指令执行时间是程序时间复杂度基本单位

各种计算机指令都由有限个微指令组成。因而微指令是计算机最基本的指令。微指令的执行需要固定的时间段。它由计算机所有控制线值变化的时间段来确定。这种时间段又被称为节拍。

节拍是计算机程序运行时间的基本单位。一个问题解决的程序可以用其得到结果之后，一共用多少个节拍来衡量运行时间的长短。同一问题可以有不同的程序来解决。同一个问题不同程序运行时间的长短就是衡量程序设计得好坏的重要指标。

3. 控制线求解的多项式

逻辑多项式j_i=f(x₀,x₁,…,x_m)，j_i是控制线逻辑多项式f(x₀,x₁,…,x_m)的逻辑值，x_k是时钟或标志线逻辑变量；i=0,1,2,3,…n；k=0,1,2,…,m。

控制线j_i的值是由逻辑多项式f(x₀,x₁,…,x_m)来确定的。求解j_i的值的多项式是根据表1的真值来完成的。f(x₀,x₁,…,x_m)是由x_k变量或其非x_k^'形成的与运算表示。表中自变量值为1取变量本身，值为0取其非表达，显然得到一个与逻辑项。而每一节拍得到的J=F(j₀,j₁,j₂,…,j_n)是n+1位值就是微指令。

表1   计算机控制矩阵真值表(空白为0）

一个节拍一般是由一个节拍逻辑自变量x_k=1来表示的。

4. 程序的执行时间复杂度

同一个问题编写的程序执行起来有快有慢，好的方法编写的程序解决问题就快，否则就慢。

求得问题结果的算法基本有两种。一种是按着确定的推断方式，一步一步地得出结果。这种方式在算法复杂度被总结出是多项式形式时间，用Ο(n^k)表示。另一种算法叫猜测验证法，就是先猜测问题的结果，然后再设法验证。验证问题一般都是随意选择可能发生的多种状态中一种，一步步地找到猜测的结果，或者否定猜测的结果。这种方法被算法复杂性总结为指数形式时间复杂度，记为Ο(cⁿ）。这两种表达式中k和c是常量，n是变量，n=1,2,3,…。

5. 计算机解题的时间复杂度

一个确定型图灵机，实际上就是一个计算机能够求得问题结果的程序。这种程序是靠推演的方式来解决确定问题结果的，不必面面俱到。因而其算法时间复杂度为Ο(n^k)。

而非确定型图灵机是猜测验证解题的代表，因而其算法时间复杂度应是Ο(cⁿ），因为其每一步的各种情况都需要验证。

不论Ο(n^k)还是Ο(cⁿ），只要n是一个常数，那么它们就都变成了Ο(1)的常数多项式复杂度时间。

现代计算机实际上是集确定型和非确定型图灵机于一身的计算机。因而可以用推断和猜测验证两种方法进行问题处理。同两种图灵机一样，计算机对一切可解问题的处理都会在有限个状态中完成。

计算机结构确定之后，全体可变化的基本状态是由它的控制线全体的所有可能变化值确定的。有了状态变化有限性，那么问题算法中时间复杂度的n就是与算法有关的常量。这样就有了Ο(cⁿ）=Ο(n^k)。

讨论计算机就会更加深刻地说明图灵机的原理和方法。从程序和数据存储的思想出发，所有的计算机设计都成了微指令设计，即微指令选择的问题。

机器指令是由有限个微指令构成的例行程序，因而机器指令的执行时间也是多项式时间。高级语言指令是由有限个机器指令组成的例行程序，故而其执行也是多项式时间。

计算机语言程序是由有限个指令构成的，因而任何计算机可解问题的正确程序执行都是多项式时间。

从这个方面去理解P/NP问题会简单许多。

2014-10-19稍加修改