SEP：可计算性与复杂性（二） (5-4)

对于一个输入ω，设n＝|ω| 为ω的长度。根据(Hartmanis, 1989)，我们说一个图灵机M的，运行所需时间为(runs in time) T(n)，如果，对于所有n长的ω，M(ω) 最多需要 T(n)步然后停机。这就被称为最坏情况复杂度，因为 T(n)必须不小于，在长度为n的任何输入上所需的时间。

对于任何一个函数，T：N → N，使得

TlME[T(n)]＝{A│A＝L(M)for some M thαt runs in time T(n)}.

Alan Cobham与Jack Edmonds确定了复杂度的P类，其为在一定多项式时间量(polynomial amount of time)中可识别的问题。这已是一个很好的数学工具，涵盖了可行问题的类，即所有这些问题的中等大小的实例都可以被识别出来，

P＝∪TlME[nⁱ]

i＝1，2，. . .

任何不在P中的问题，都是一定不可行的。而另一方面，有算法在P中的那些自然的问题，都倾向于，最终会有一个，被发现对这些问题实际可行的算法。

许多重要的包括在P中的计算复杂性类，都已被定义与研究，而少数则是NP，PSPACE，及EXPTlME。PSPACE包括那些，用多项式存储空间量(polynomial amount of memory space)可解的问题。EXPTlME是关于，在时间2⁽p(n))上可解的一些多项式p的集。

或许上面最有意思的类是NP：非确定性多项式时间(nondeterministic polynomial time)。其定义不是来自于一台真实的机器，而是一个数学抽象。一个非确定性图灵机N，其在每一步的两个可能行动中做出(猜测)一个选择，如果在输入ω上，这些选择的某个序列是可接受的，那么我们说N接受ω，以及我们说，N在输入ω上花了非确定的时间就是在这个导向接受的序列中所花的步数。非确定性机器不计所有其他的可能选择，而只计正确选择的单个序列。

NP时常被描绘为问题集S，其带有元素关系(membership)的简短证明。比如，假设我们被给定了关于m大小的自然数，α₁，. . .，αₘ及一个目标数t$$，的一个列表。这是一个子集和问题(Subset Sum problem)的实例：是否存在一个元素为m个数的子集，其和正好是t？在非确定性线性时间中，这个问题非常容易解决：对于每一个i，我们猜其是否取αᵢ。然后我们加上所有我们决定去取的数，如果上面的和等于t那么就接受。因此，这个非确定性时间是线性的，即，某个常值乘以输入的长度n。然而在此没有一种已知的(确定性)方法，可以在小于n的指数级时间内，去解决这个问题。

现在已经有了大量关于算法的研究，并且一些重要问题的复杂度也得到了很好的理解。尤其是，对问题间的还原进行了定义，并用其去比较两个问题的相对难度。直观地，我们说A是可还原(reducible)到B上的(A ≤ B) ，如果有一个简单的翻译τ，以一种保持元素关系的方式，将A的实例映射为B的实例，即，τ(ω) ∈ B ⇔ ω ∈ A。

值得注意的是，多数自然发生的计算问题，都被证明为，对上述的其中一个类中完全的(一个问题A，对一个复杂性类C是完全的，当，A是C中的一个成员，而C中的所有其他元素B不难于A，即，B ≤ A。两个对于同一个类而完全的问题拥有相等的复杂度。)

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