Thursday, 12 April 2018

Дарвинистам - горячий привет!

Теорема. Любая строка длиной N имеет колмогоровскую сложность не более N + O(1).

Следовательно, не существует алгоритма, который бы выдавал строку колмогоровской сложности, превышающей колмогоровскую сложность самого алгоритма.

Это 5, как говорится. Больше по этому поводу и писать-то нечего.

No comments:

Post a Comment