描述复杂性理论

计算复杂性理论是理论计算机科学的分支学科之一，是指使用数学方法对计算中所需的各种资源的耗费作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。用算法作工具来研究字符串所含的信息（即串的描述复杂度）的理论，又称算法信息论。由于各种计算对象都可以用0，1组成的字符串(简称0，1串)来表示。任何计算过程（包括证明过程）都可转化为对串的加工过程，在这个过程中串不断地变换，所含信息也在变化，因此分析这种变化就能揭示计算和证明过程的某些内在属性。在这种意义下可认为描述复杂性理论是把算法与信息结合起来的理论。　描述复杂度 0，1串x所含信息可用对x的描述之长短来刻划，可以认为串x的描述是构造x的指令组，串x的描述复杂度可直观地定义为生成x的最短程序之长，记作K(x)。这个程序无输入，其输出为x。