在算法信息论（计算机科学和数学的一个分支）中，一个对象比如一段文字的柯氏复杂性（亦作柯尔莫哥洛夫复杂性、描述复杂性、柯尔莫哥洛夫-柴廷复杂度、随机复杂度，或算法熵）是衡量描述这个对象所需要的信息量的一个尺度。柯氏复杂性是由安德雷·柯尔莫哥洛夫于1963年发现，所以用他的名字命名。
定义
柯氏复杂度可以适用于任何数学概念，但是本文只针对字符串。首先需要确定我们用以描述字符串的语言，它可以基于任何计算机语言，例如LISP、
Pascal或
Java字节码。如果P是一个可以输出字符串x的程序，则P是x的描述。描述长度就等于程序P作为字符串的长度，乘上每个字符的比特数。（例如，对于
ASCII来说是7）
我们也可以使用
图灵机的编码。每一个图灵机M都对应一个字符串
。如果M是一个图灵机，给它输入字符串w它会输出字符串x，那么这段拼合起来的字符串 +w就是x的描述。这种描述更适合比较严谨的证明，通常是在正式研究中才会使用。在本文的讨论中会使用比较非正式的描述。对于任何一个字符串s，都存在至少一个描述。可以用以下程序表示：
如果s的描述d(s) 长度达到最小（即使用最少的比特数），它就可以称为s的“最小描述”。同时，d(s)的长度（也就是这个描述使用的比特数）就是s的“柯氏复杂度”，写作K(s)。可以表示为：
最小描述长度取决于选择什么语言来描述；但是改变描述语言所带来的长度变化是有限的，这个属性称作不变性理论（invariance theorem）。
不变性理论
非正式表述
一些描述语言可以被称作“最优的”（optimal）。它们有如下属性：给定任意一个描述语言来描述一个对象，我们也可以用最优描述语言来描述该对象，只需要在原来的那段描述前面加上一段固定的前缀。这段前缀仅仅取决于使用哪一种描述语言，不取决于对对象的描述，也不取决于被描述的对象。
以下是“最优描述语言”（Optimal description language）的一个例子。这个语言中的描述都会包括以下两部分：
更技术性的说法是，第一部分是一段计算机程序，如果把第二部分输入这个程序，就会输出该对象。
不变性理论指的是：对于任意的描述语言L，最优描述语言都至少和L同样有效，但是会增加一段固定的前缀。
证明： 对于以L作为描述语言的任意一段描述D，D都可以转换成为最优描述语言下的一段描述，这段描述包括将L描述为一段计算机程序P（前面提到的第一部分），然后将原来的描述D作为这段程序的输入（第二部分）。新的描述D’ 的长度（近似值）为：
P的长度为常数，不取决于D，所以，至多有一个常量项长度的前缀，不取决于描述对象。所以，最优描述语言在
up to固定前缀的意义上是通用的。
更正式的描述
K1和K2是满足
图灵完备性的描述语言L1和L2的复杂度函数，则存在一个常数c，仅取决于对于语言L1和L2的选择，有：
证明：根据对称性，可以证明存在一个常数c对于所有的字符串s满足：
然后，假设语言L1中存在一个程序，相当于是L2的
解释器:
function InterpretLanguage(string p)
其中p是L2中的一个程序。解释器有以下属性：
然后，设L2中的程序P是s的最小描述，则InterpretLanguage(P) 将会返回字符串s。而s的描述长度，是以下两项之和：
以上证明了所需的上界。
历史与背景
算法信息论是计算机科学中的一个领域，研究柯氏复杂性和其他对于字符串（或者其他数据结构）的复杂性度量。
柯氏复杂性的理论和概念基于雷·所罗门诺夫的一些关键性理论。1960年，所罗门诺夫发表了《归纳推理的通用性理论导论》，作为他所创立的算法概率论的一部分。在1964年发表的《信息与控制》的第一和第二部分 “归纳推理的正式理论” 中，他给出了一个更完整的描述。
安德雷·柯尔莫戈洛夫稍后于1965年在Problems Inform. Transmission上独立发表了这一理论。格里高利·柴廷也在J. ACM上发表了这一理论——柴廷的论文提交于1966年10月，于1968年12月修订，引用了所罗门诺夫和柯尔莫戈洛夫的论文。
这个理论认为，在所有从对字符串的描述中解码出字符串的算法里，存在一个最优的算法。这个算法对于所有的字符串来说，都可以得到和其他算法同样短的代码，除去一段固定的附加代码，这段代码不取决于字符串，只取决于所选择的算法。所罗门诺夫用这个算法和它所允许的代码长度，定义了一个字符串的“普适概率”universal probability，以对字符串行的归纳推断作为基础。柯尔莫哥诺夫利用这个理论定义了字符串的很多属性，包括复杂度、随机度和信息。
当柯尔莫戈洛夫了解到所罗门诺夫的工作之后，承认了所罗门诺夫的
发现在先。在很长一段时间内，所罗门诺夫的工作在苏联比在西方更为人知晓。科学界的共识一般是把和复杂度有关的工作归功于柯尔莫戈洛夫，因为他主要研究串行的随机程度；而算法信息论的工作则归功于所罗门诺夫，他主要集中研究用普适概率分布来进行串行预测。这两个领域的边界，包括描述复杂度和概率通常被称为柯尔莫戈洛夫复杂度。计算机科学家李明认为这是
马太效应的体现。
柯尔莫戈洛夫复杂度或者算法信息论有很多变体，其中一个广泛应用的概念是“自生成程序”self-delimiting-program，主要来自于里奥尼德·列文（1974）。
Mark Burgin基于
布鲁姆公理（Blum 1967），对于柯氏复杂度进行了公理化（Burgin 1982）。
基本结论
在以下讨论中，我们用K(s) 来表示字符串s的复杂度。
显而易见，一个字符串的最小描述不可能超过字符串本身的长度太多。上文中的程序GenerateFixedString可以输出s，长度比s稍长。
定理：存在一个常数c，使得：
柯氏复杂性的不可计算性
定理：存在字符串，拥有任意大的柯氏复杂度。严格表述为：对于任意n∈ ℕ，存在一个字符串s的复杂度K(s) ≥n
证明：反证。如果定理不成立，则任意的无限长字符串，都可以使用有限个数，复杂性小于n比特的程序来生成了。
定理：K不是一个
可计算函数。也就是说，不存在一个程序，可以把字符串s作为输入，然后输出它的K(s)。
证明：以下的反证法将使用类似Pascal语言的代码。为了证明的简单起见，该语言的描述（即其解释器）大概有1,400,000比特。下面开始反证法，假设有这样一个程序存在：
它可以把字符串s作为输入，然后输出它的K(s)；简单起见，假设这一函数的长度是7,000,000,000比特。考虑另一段长度为1,288比特的程序：
它将KolmogorovComplexity作为子程序，这个程序会从短到长检查所有的字符串，直到找到一个复杂度至少有8,000,000,000比特的字符串s。这也就意味着，任何短于8,000,000,000比特的程序都不可能输出这个字符串。但是，以上的整个程序能够输出s，而其长度却只有7,001,401,288比特，反证完毕。（如果KolmogorovComplexity的代码要更短一些，反证依然成立。如果它要更长，那么GenerateComplexString中使用的常数也可以相应变大。）
以上使用的反证法类似于佩里悖论：“1不2能3用4少5于6二7十8个9字10定11义12的13最14小15整16数”。也可以使用停机问题H的不可计算性来推导K的不可计算性，因为K和H是
图灵等价的。
它的一个结论，在程序员群体中被幽默地称为充分就业定理，其涵义之一是指不存在一个最优的规模优选编译器。
柯氏复杂性的链式法则
柯氏复杂性的链式法则，是指：
它说明，能够输出X和Y的最短程序，相当于输出X和已知X的情况下可以输出Y的程序之和再加上一个对数参数。使用这个法则，可以定义柯氏复杂性的
互信息近似。
数据压缩
计算K(s)的上界很简单：只需要使用某种算法
压缩字符串s，再把所选语言中的压缩算法加上压缩后的字符串，它们的和就是长度上界。其实这就相当于给定语言中的自解压缩档。
如果一个字符串s的一个描述长度不超过 |s|−c比特，则可以说这个字符串可以被压缩掉c。这相当于说K(s) ≤ |s|-c。否则的话，我们就说s不能被压缩掉c。如果一个字符串不能被压缩掉1，那么我们就说这个字符串是不可压缩的。根据
鸽巢原理，每一个压缩后的字符串对应唯一的压缩前的字符串，所以不可压缩串一定存在。因为长度为n的字符串有 2个，但是只存在 2- 1 个长度小于n的字符串， (i.e. 长度可能为 0,1,...,n−1)。
由于同样的理由，大部分的字符串都是复杂的，也就是说难以被显著地压缩，它们的K(s)并不比 |s|，s的长度小多少。准确地说，对于任意的n，有 2个长度为n的字符串。在这些字符串的样本空间中的离散型均匀分布表明，对于每一个长度为n的字符串，权重为 2。
定理：对于长度为n的字符串组成的样本空间的离散型均匀分布来说，一个串不能被压缩以c的概率至少为 1 - 2+ 2。
证明：所有描述长度不超过n-c的字符串的数量，可以由以下等比数列得到：
那么，还剩下至少：
个长度为n的字符串不能够被压缩以c。对于单个字符串的概率，应该除以 2。