|
|
Колмогоровский семинар по сложности вычислений и сложности определений
16 декабря 2013 г. 16:45–18:25, г. Москва, Главное здание МГУ, ауд. 16-04
|
|
|
|
|
|
Коммуникационная сложность приближенного вычисления колмогоровской сложности
Н. К. Верещагин |
Количество просмотров: |
Эта страница: | 260 |
|
Аннотация:
Алисе дается слово x, Бобу - слово y (оба слова имеют длину n и составлены из нулей и единиц). Алиса и Боб должны с некоторой данной точностью e найти колмогоровскую сложность пары (x,y). Несложно установить, что для детерминированных коммуникационных протоколов для этого необходимо передать в худшем случае не менее n-2e-O(1) битов. Мы доказываем, что похожая оценка верна и для вероятностных протоколов. А именно, если вероятностный протокол для любой исходной пары слов с вероятностью не менее 0.01 находит приближение к сложности исходной пары с точностью epsilon n/ log n, то на какой-то входной паре он передает не менее 0.99n битов.
|
|