在算法信息论（计算机科学和数学的一个分支）中，一个对象比如一段文字的柯氏复杂性（亦作柯尔莫哥洛夫复杂性、描述复杂性、柯尔莫哥洛夫-柴廷（英语：Gregory Chaitin）复杂度、随机复杂度，或算法熵）是衡量描述这个对象所需要的信息量的一个尺度。柯氏复杂性是由安德雷·柯尔莫哥洛夫于1963年发现，所以用他的名字命名。
以下面的两个长度为64的字符串为例。
0101010101010101010101010101010101010101010101010101010101010101
1100100001100001110111101110110011111010010000100101011110010110
第一个字符串可以用中文简短地描述为“重复32个‘01’”。第二个字符串没有明显的简短描述。
一个字符串的程序，则 P 是 的描述。描述长度就等于程序 P 作为字符串的长度，乘上每个字符的比特数。（例如，对于 ASCII来说是7）
我们也可以使用图灵机的编码。每一个图灵机 M 都对应一个字符串 <M>。如果 M 是一个图灵机，给它输入字符串 它会输出字符串 ，那么这段拼合起来的字符串 <M>＋ 就是 的描述。这种描述更适合比较严谨的证明，通常是在正式研究中才会使用。在本文的讨论中会使用比较非正式的描述。
对于任何一个字符串 ，都存在至少一个描述。可以用以下程序表示：
function GenerateFixedString() return
如果 的描述 () 长度达到最小（即使用最少的比特数），它就可以称为 的“最小描述”。同时，()的长度（也就是这个描述使用的比特数）就是 的“柯氏复杂度”，写作 ()。可以表示为：
最小描述长度取决于选择什么语言来描述；但是改变描述语言所带来的长度变化是有限的，这个属性称作不变性理论（invariance theorem）。
一些描述语言可以被称作“最优的”（optimal）。它们有如下属性：给定任意一个描述语言来描述一个对象，我们也可以用最优描述语言来描述该对象，只需要在原来的那段描述前面加上一段固定的前缀。这段前缀仅仅取决于使用哪一种描述语言，不取决于对对象的描述，也不取决于被描述的对象。
以下是“最优描述语言”（Optimal description language）的一个例子。这个语言中的描述都会包括以下两部分：
更技术性的说法是，第一部分是一段计算机程序，如果把第二部分输入这个程序，就会输出该对象。
不变性理论指的是：对于任意的描述语言 ，最优描述语言都至少和 同样有效，但是会增加一段固定的前缀。
证明： 对于以作为描述语言的任意一段描述 ， 都可以转换成为最优描述语言下的一段描述，这段描述包括将 描述为一段计算机程序 （前面提到的第一部分），然后将原来的描述 作为这段程序的输入（第二部分）。新的描述 ’ 的长度（近似值）为：
的长度为常数，不取决于 ，所以，至多有一个常数项长度的前缀，不取决于描述对象。所以，最优描述语言在up to固定前缀的意义上是通用的。
"'定理"'：设 1 和 2 是满足 图灵完备性的描述语言 1 和 2的复杂度函数，则存在一个常数 ，仅取决于对于语言 1 和 2 的选择，有：
证明：根据对称性，可以证明存在一个常数 对于所有的字符串 满足：
然后，假设语言 1 中存在一个程序，相当于是 2 的解释器:
function InterpretLanguage(string )
其中 是 2 中的一个程序。解释器有以下属性：
然后，设 2 中的程序 P 是 的最小描述，则 InterpretLanguage(P) 将会返回字符串 。而 的描述长度，是以下两项之和：
以上证明了所需的上界。
算法信息论是计算机科学中的一个领域，研究柯氏复杂性和其他对于字符串（或者其他数据结构）的复杂性度量。
柯氏复杂性的理论和概念基于雷·所罗门诺夫（英语：Ray Solomonoff）的一些关键性理论。1960年，所罗门诺夫发表了《归纳推理的通用性理论导论》，作为他所创立的算法概率论（英语：Algorithmic probalility）的一部分。在1964年发表的《信息与控制》的第一和第二部分 “归纳推理的正式理论” 中，他给出了一个更完整的描述。
安德雷·柯尔莫戈洛夫稍后于1965年在 上独立发表了这一理论。格里高利·柴廷也在 上发表了这一理论——柴廷的论文提交于1966年10月，于1968年12月修订，引用了所罗门诺夫和柯尔莫戈洛夫的论文。
这个理论认为，在所有从对字符串的描述中解码出字符串的算法里，存在一个最优的算法。这个算法对于所有的字符串来说，都可以得到和其他算法同样短的代码，除去一段固定的附加代码，这段代码不取决于字符串，只取决于所选择的算法。所罗门诺夫用这个算法和它所允许的代码长度，定义了一个字符串的“普适概率”universal probability，以对字符串行的归纳推断作为基础。柯尔莫哥诺夫利用这个理论定义了字符串的很多属性，包括复杂度、随机度和信息。
当柯尔莫戈洛夫了解到所罗门诺夫的工作之后，承认了所罗门诺夫的发现在先。在很长一段时间内，所罗门诺夫的工作在苏联比在西方更为人知晓。科学界的共识一般是把和复杂度有关的工作归功于柯尔莫戈洛夫，因为他主要研究串行的随机程度；而算法信息论的工作则归功于所罗门诺夫，他主要集中研究用普适概率分布来进行串行预测。这两个领域的边界，包括描述复杂度和概率通常被称为柯尔莫戈洛夫复杂度。计算机科学家李明认为这是马太效应的体现。
柯尔莫戈洛夫复杂度或者算法信息论有很多变体，其中一个广泛应用的概念是“自生成程序”self-delimiting-program，主要来自于里奥尼德·列文（英语：Leonid Levin）（1974）。
Mark Burgin基于布鲁姆公理（英语：Blum axioms）（Blum 1967），对于柯氏复杂度进行了公理化（Burgin 1982）。
在以下讨论中，我们用 () 来表示字符串 的复杂度。
显而易见，一个字符串的最小描述不可能超过字符串本身的长度太多。上文中的程序GenerateFixedString 可以输出 ，长度比 稍长。
定理：存在一个常数 ，使得：
定理：存在字符串，拥有任意大的柯氏复杂度。严格表述为：对于任意 ∈ ℕ，存在一个字符串 的复杂度 () ≥
证明：反证。如果定理不成立，则任意的无限长字符串，都可以使用有限个数，复杂性小于 比特的程序 来生成了。
定理： 不是一个可计算函数。也就是说，不存在一个程序，可以把字符串 作为输入，然后输出它的 ()。
证明：以下的反证法将使用类似Pascal语言的代码。为了证明的简单起见，该语言的描述（即其解释器）大概有 7006140000000000000♠1400000 比特。下面开始反证法，假设有这样一个程序存在：
function KolmogorovComplexity(string s)
它可以把字符串 作为输入，然后输出它的 ()；简单起见，假设这一函数的长度是 7009700000000000000♠7000000000 比特。现在考虑另一段长度为 7003128800000000000♠1288 比特的程序：
function GenerateComplexString() for i = 1 to infinity: for each string s of length exactly i if KolmogorovComplexity(s) >= 8000000000 return s
它将 KolmogorovComplexity 作为子程序，这个程序会从短到长检查所有的字符串，直到找到一个复杂度至少有 7009800000000000000♠8000000000 比特的字符串 。这也就意味着，任何短于 7009800000000000000♠8000000000 比特的程序都不可能输出这个字符串。但是，以上的整个程序能够输出 ，而其长度却只有7009700140128800000♠7001401288 比特，反证完毕。（如果 KolmogorovComplexity 的代码要更短一些，反证依然成立。如果它要更长，那么 GenerateComplexString 中使用的常数也可以相应变大。）
以上使用的反证法类似于佩里悖论（英语：Berry paradox）：“1不 2能 3用 4少 5于 6二 7十 8个 9字 10定 11义 12的 13最 14小 15整 16数”。也可以使用停机问题 的不可计算性来推导 的不可计算性，因为 和 是图灵等价的。
它的一个结论，在程序员群体中被幽默地称为充分就业定理（英语：Full employment theorem），其涵义之一是指不存在一个最优的规模优选编译器。
柯氏复杂性的链式法则，是指：
它说明，能够输出 和 的最短程序，相当于输出 和已知 的情况下可以输出 的程序之和再加上一个对数参数。使用这个法则，可以定义柯氏复杂性的互信息近似。
计算 ()的上界很简单：只需要使用某种算法压缩字符串 ，再把所选语言中的压缩算法加上压缩后的字符串，它们的和就是长度上界。其实这就相当于给定语言中的自解压缩档。
如果一个字符串 的一个描述长度不超过 ||− 比特，则可以说这个字符串可以被压缩掉 。这相当于说 () ≤ ||-。否则的话，我们就说 不能被压缩掉 。如果一个字符串不能被压缩掉1，那么我们就说这个字符串是 。根据鸽巢原理，每一个压缩后的字符串对应唯一的压缩前的字符串，所以不可压缩串（英语：incompressible string）一定存在。因为长度为 的字符串有 2 个，但是只存在 2 - 1 个长度小于 的字符串， (i.e. 长度可能为 0,1,...,
由于同样的理由，大部分的字符串都是复杂的，也就是说难以被显著地压缩，它们的 ()并不比 ||， 的长度小多少。准确地说，对于任意的 ，有 2 个长度为 的字符串。在这些字符串的样本空间中的离散型均匀分布表明，对于每一个长度为 的字符串，权重为 2− 。
定理：对于长度为 的字符串组成的样本空间的离散型均匀分布来说，一个串不能被压缩以 的概率至少为 1 - 2−+1 + 2−。
证明：所有描述长度不超过 - 的字符串的数量，可以由以下等比数列得到：
那么，还剩下至少：
个长度为 的字符串不能够被压缩以 。对于单个字符串的概率，应该除以 2 。
我们已经知道，在所有可能的字符串里，大部分的串都是复杂的，也就是说它们不能被显著地压缩。然而，如果一个串的复杂度超过了某个阈值，则它不能被形式化地证明为复杂的。形式化的证明如下：首先，为自然数创建一个公理系统 S 。这个公理系统需要足够强，可以判定关于字符串复杂度的断言 A ，并且和 S 中的 FA 相关联。这个关联需要有以下属性：
如果 FA可以被 S 中的定理证明，则相对应的断言 A 为真。这个“形式化”可以用人工编码例如哥德尔数的方法实现，或者依照对于 S 的预期解释来进行形式化。
定理：存在一个常数 （ 仅取决于特定的公理系统以及描述语言的选择），使得没有任何一个 满足以下情况：
可以在公理系统 S 中证明。
考虑到占多数的几乎不可压缩的串，大部分这样的情况都会成立。
这个结论的证明脱胎于佩里悖论中使用的自指结构。使用反证法，如果定理不成立，则：
我们可以使用以下方式列举 S 中的所有形式化证明
function NthProof(int )
它接受输入 ，然后输出一个证明。这个函数会列举所有的证明，有一些证明是针对我们并不关心的一些公式，尽管在 S 的语言中所有可能的证明都是关于某个 的。其中有一些证明是针对复杂度公式 () ≥ ，其中 和 都是语言 S 中的常数。以下程序
function NthProofProvesComplexityFormula(int )
可以确定，第 个证明是否证明了复杂度公式 () ≥ 。字符串 和整数 分别可以由以下程序计算：
function StringNthProof(int )
function ComplexityLowerBoundNthProof(int )
考虑以下程序：
function GenerateProvablyComplexString(int ) for i = 1 to infinity: if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ return StringNthProof()
对于给定的 ，这个程序会尝试所有的证明，直到找到一个字符串以及 S 中关于公式() ≥ （其中 ≥ ）的形式证明。如果假设（X）成立，那么这个程序会停止。这个程序的长度为 . 存在一个整数 0 使得 + log2(0) + < 0，其中 是以下程序的前缀：
function GenerateProvablyParadoxicalString() return GenerateProvablyComplexString(0)
（注意 0 是直接包含在以上函数中的，而前面的 log2(0) 已经包含了它） 程序 GenerateProvablyParadoxicalString 输出的字符串 ，存在一个 使得 () ≥ 可以在 S 中形式化证明，且 ≥ 0。所以，() ≥ 0 成立。但是， 也可以被长度为 + log2(0) + 的程序描述，所以它的复杂度小于 0。以上矛盾证明了 假设 (X) 不能成立。
