Вывод вероятности для нижней границы алгоритмической сложности

Событие сучайного возникновения конфигураций материи Х, характеризующихся значениями алгоритмической сложности ASC(X,C,P) ≥ α, экспоненциально редко:

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α.

Доказательство. По определению, алгоритмическая сложность есть разница информации в Х и колмогоровской сложности Х в контексте С:

ASC(X,C,P) = I(X) − K(X|C).

( Read more... )