柯尔莫哥洛夫复杂度简称柯西复杂度，给出了描述该对象所需计算资源的一种度量。这一思想由苏联数学家A.N.柯尔莫哥洛夫、美国学者R.索洛莫洛夫以及G.蔡廷等3人几乎同时独立提出。

考虑下述两个32位长的字符串：①cdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd；②3jieq24kosijqpnmcxsdpwo29sdtpwed。第一个字符串有一个简短的描述“16个cd”，而第二个字符串没有明显的规律，描述它需要32个字符。因此，第一个字符串的柯西复杂度低于第二个字符串。一般地，一个字符串的复杂度是指在特定描述语言下该字符串的最短可能描述长度。柯西复杂度可以用来描述任意的数学对象，文中仅以字符串作为示例。

首先指定描述语言，它可以为任意的计算机编程语言，如Java语言或者C语言。如果P是一个程序并输出字符串s，那么P为s的一个描述，该描述的长度为程序P的长度。字符串s的柯西复杂度K(s)为描述s的所有程序中最短的那个程序的长度。最短描述长度与所选的描述语言相关，但描述语言的选择对柯西复杂度的影响是有限的。

给定描述语言L，对于任意的字符串s，用最优描述语言描述s的柯西复杂度与用L描述s的柯西复杂度之间相差一个常量。因此，虽然柯西复杂度的定义与特定的描述语言相关，但它的定义却具有通用性。柯西复杂度的一些基本性质如下所述：①对于任意字符串s，存在一个常量c，使得K(s)≤|s|+c。②存在一个字符串s，其柯西复杂度K(s)可以任意大。③柯西复杂度K(s)不是一个可计算的函数，即不存在一个计算机程序以字符串s为输入，以其柯西复杂度K(s)为输出。④K(X,Y)≤K(X)+K(Y|X)+O[logK(X,Y)]，柯西复杂度的链式法则表明，用来描述X和Y的最短程序比分别用来描述X的最短程序和描述Y的最短程序之和相差一个对数项。⑤随机序列的柯西复杂度的数学期望值接近于香农熵。

如果一个字符串s有一个长度不超过|s|-c的描述（即K(s)≤|s|-c），则称s是可压缩的；否则，称s是不可压缩的。不可压缩字符串是必然存在的，因为长度为n的二元字符串一共有2ⁿ个，但长度小于n的所有二元字符串一共只有2ⁿ-1个。大多数字符串是复杂的，因为它们不能被大幅度地压缩，即K(s)不比字符串s的长度小很多。虽然存在一些简单的字符串序列，但大多数序列都是不可压缩的。如果随机选取一个字符串序列，那么这个序列将以大概率是一个复杂序列。