Аннотация:
Алисе дается слово x, Бобу - слово y (оба слова имеют длину n и составлены из нулей и единиц). Алиса и Боб должны с некоторой данной точностью e найти колмогоровскую сложность пары (x,y). Несложно установить, что для детерминированных коммуникационных протоколов для этого необходимо передать в худшем случае не менее n-2e-O(1) битов. Мы доказываем, что похожая оценка верна и для вероятностных протоколов. А именно, если вероятностный протокол для любой исходной пары слов с вероятностью не менее 0.01 находит приближение к сложности исходной пары с точностью epsilon n/ log n, то на какой-то входной паре он передает не менее 0.99n битов.
|
