描述复杂性（descriptive complexity），理学-计算机科学技术-计算机科学理论-计算复杂性，在图灵机上产生一个给定输出所需要的最短输入的长度。又称柯尔莫哥洛夫复杂性。考虑长度为的0-1字符串（简称0-1串或串），这样的串有个，但是长度不超过的0-1串只有个。所以，无论采用何种压缩手段，只要这种压缩是无损的（即一对一的，或数学上所说的单射），在每一个长度上，都一定有不能压缩得更短的串。如果把压缩手段限定为图灵机，一个串所能被压缩到的最短串的长度，就称为这个串的描述复杂性（descriptive complexity）或者柯尔莫哥洛夫复杂性（见柯尔莫哥洛夫复杂度）。形式化地，相对于图灵机，串的描述复杂性等于最短的串的长度，使得图灵机以为输入最终停机并输出。当不存在这样的时，就定义为无穷大。在历史上，A.N.科尔莫戈罗夫（又译柯尔莫哥洛夫）、G.J.柴廷（Gregory John Chaitin，1947-06-25～ ）、克劳德（Claude）三人独立地提出了描述复杂性的概念。