柯氏复杂性 在算法信息论计算机科学和数学的一个分支中一个对象比如一段文字的柯氏复杂性亦作柯尔莫哥洛夫复杂性描述复杂性柯尔莫哥洛夫柴廷英语Gregory Chaitin复杂度随机复杂度或算法熵是衡量描述这个对象所需要的信息量的一个尺度柯氏复杂性是由安德雷柯尔莫哥洛夫于年发现所以用他的名字命名 以下面的两个长度为的字符串为例   第一个字符串可以用中文简短地描述为重复个第二个字符串没有明显的简短描述 一个字符串 s displaystyle s 的柯氏复杂性 C  s  displaystyle Cs 或者 K  s  displaystyle Ks 区别如后是这个字符串的最短描述的长度换言之一个字符串 s displaystyle s 的柯氏复杂性是能够输出且仅输出这个字符串的最短计算机图灵机程序的长度 这样的定义导致在使用不同的描述语言或者不同的图灵机的时候柯氏复杂性不一样所以在讨论柯氏复杂性的时候通常都事先固定一个通用图灵机 U displaystyle U 作为参照可以证明在使用 U displaystyle U 做参照的时候对任意的图灵机 M displaystyle M 都存在一个仅决定于 U displaystyle U 和 M displaystyle M 的常数 c M displaystyle cM 使得对所有的字符串 s displaystyle s 相对于 U displaystyle U 的柯氏复杂性 C U displaystyle CU 或者 K U displaystyle KU 和相对于 M displaystyle M 的柯氏复杂性 C M displaystyle CM 或者 K M displaystyle KM 都满足 C U  s   C M  s   c M displaystyle CUsleq CMscM 根据这点通常确定了一个参照图灵机后就用 C displaystyle C 和 K displaystyle K 表示柯氏复杂性省略 U displaystyle U  不难证明任何字符串的柯氏复杂度都不会比字符串自身的长度超过太多类似与上文中的字符串它的柯氏复杂度和字符串的长度关系不大因此并不复杂 與康托尔的对角论证法哥德尔不完备定理和图灵的停机问题類似柯氏复杂度的概念可以用于阐述和证明不可能性