什么是描述复杂性理论?

[拼音]：miaoshu fuzaxing lilun

[外文]：theory of description complexity

用算法作工具来研究字符串所含的信息（即串的描述复杂度）的理论，又称算法信息论。由于各种计算对象都可以用0，1组成的字符串(简称0，1串)来表示。任何计算过程（包括证明过程）都可转化为对串的加工过程，在这个过程中串不断地变换，所含信息也在变化，因此分析这种变化就能揭示计算和证明过程的某些内在属性。在这种意义下可认为描述复杂性理论是把算法与信息结合起来的理论。

0，1串x所含信息可用对x的描述之长短来刻划，可以认为串x的描述是构造x的指令组，串x的描述复杂度可直观地定义为生成x的最短程序之长，记作K(x)。这个程序无输入，其输出为x。

作为普遍定义，K(x)必须客观地反映x所含信息多少，不会由于采用不同计算模型下的程序概念而使对应的K(x)值截然不同。在可计算理论中已证明，现存的不同的计算模型A，B之间可以相互模拟，于是A模型下的程序PA结合模拟程序后，就成为B模型下的程序PB，因此在相差一个常数的意义下K(x)值是唯一确定的。

描述复杂性理论是在可计算性理论的发展和计算机广泛应用的推动下发展起来的。60年代A.H.柯尔莫戈罗夫与柴廷各自独立地提出描述复杂度概念，用以定义数的随机性，并能较全面地提出关于程序长度的描述复杂性理论。

描述复杂性理论的研究对象是0，1串以及它们变换时所含信息的变化。它可用于研究形式系统，分析公理所含信息与它推出的定理所含信息之间的关系，也可用于研究计算过程，从而得出计算所耗费资源的下界（见计算复杂性理论）和时间与空间的折换关系。

这个理论中大部分结果的证明是非构造性的，只从逻辑上推断特定对象的存在性，并不具体构造出哪个对象。这种证明过程常遵循下述模式:对待证命题A采用反证法，利用逆命题“¬A成立”这事实来对已知复杂度为K的串x构作一个生成x的较短程序P，P之长小于K，从而得出矛盾的结果。

运用这种证法可得出K(x)的下述基本性质：

（1）作为x的函数K(x)是不可计算的。

（2）长为n的串中至少有一串，它们的描述复杂度是等于n的。显然这样的串是同长串中最复杂的，称之为随机串。

柴廷1974年得出下列重要结果：对任何相容的公理化理论T，都存在一个常数CT＞0(它只依赖于T)，使K(x)＞CT这样的命题在T内是不可证的。

若把T取作数论公理系统，在T内可表达K(x)＞CT这样的命题，并且由K(x)的基本性质可知：对任何n都有长为n的串x使K(x)=n，因此当n充分大时，命题K(x)＞CT是成立的，但在T中却不可证明。由此可推出，串的随机性是不可证的。它改进了K.哥德尔关于数论公理统系不完全性定理，给出一个更具体的不可证命题：K(x)＞CT，从信息角度阐明了公理方法的局限性。

运用相似的方法可对计算复杂性下界问题得出下列结果。

考虑语言L=｛x嶅x│x为0，1串，C为异于0，1的字符｝在多带图灵机（见多带图灵机模型）上的识别问题。用T(n)，S(n)分别表示时间、空间复杂度，其中n是输入的长度。利用描述复杂性理论易于得到下述的时空折换关系：对任何一个识别L的多带图灵机，都存在常数C>0，当n充分大时，有T(n)S(n)＞Cn2。

可以证明，这样的结果是不可改进的，即对通常的S(n)都可构造一台在C′n2/S(n)时间内识别L的机器。

多头多维带单元是图灵机上线状带的推广，它允许一条带上有许多个读写头，带本身是多维的，它的基本命令允许带头沿任一方向移动一格，印出所注视符号等。这样的存储单元在功能上更接近实际存储器。考虑带头多少对计算的影响时，得到的结果是：若d1≥2，d2＜d娝，h2＜h1，而一台h2头d2维的具有跳头功能的带单元S能在T(n)时间内联机模拟一台h1头d1维单元的n条命令，则T(n)＞Cn


，其中C与ε是正常数。

它从理论上说明增多带头会节省大量时间，反之，即使增强S其他方面的能力（如带的维数加大到d娝-1，带头会一下子跳到另一带头处）也无法弥补由于减少带头而引起的恶果。

描述复杂性是研究某些性质不可证时的有力工具。通过发展、改进现有的方法，有希望对计算复杂性理论中某些重大问题提供一些方法，而且对某些具体问题的下界得出新的结果。