Аннотация:Колмогоровская сложность двоичного слова x определяется как длина кратчайшей программы, которая печатает x. Хорошо известно, что ни кратчайшая программа, ни ее длина (то есть, колмогоровская сложность исходного слова) не может быть вычислена алгоритмически по данному слову x. Поэтому возникает задача приблизительного вычисления этой программы или ее длины. Существует тривиальный алгоритм, которые по слову x длины n выдает числовой список линейной от n длины, содержащий колмогоровскую сложность x, и список экспоненциальной от n длины, состоящий из слов, одно из которых является кратчайшей программой для x. Для задачи апроксимации колмогоровской сложности ничего лучше и не придумать - если алгоритм по данному слову x длины n выдает числовой список длины l, содержащий колмогоровскую сложность x, то l должно расти линейно с ростом n. Удивительно, но для задачи апроксимации кратчайшей программы длина списка может быть существенно сокращена по сравнению с тривиальной экспоненциальной верхней оценкой: существует алгоритм, находящий по данному слову x длины n список квадратичной от n длины, содержащий кратчайшую программу для x. Более того, существует алгоритм, который за полиномиальное от n время находит некоторый список (полиномиальной длины), содержащий "почти" кратчайшую программу для x (точнее, кратчайшую с точностью до добавления O(log n) к длине программы).