Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

о нахождении максимума (прогр.)

(эта запись будет интересна программистам и математикам)

У Алисы есть число A, у Боба есть число B, оба числа n-битные. Алиса и Боб хотят сделать так, чтобы они оба знали max(A, B). Сколько бит им необходимо затратить, передавая информацию друг другу при помощи детерминистского протокола, чтобы это обеспечить?

Внимание: сообщить max(A,B) обоим участникам - это не то же самое, что сообщить, у кого из них большее число. Сделать, чтобы оба знали, у кого большее число, легко за n+1 бит: один посылает свое число другому, а тот отвечает, больше оно его собственного или меньше. Но после этого информация о max(A,B) есть только у одного из участников.

Внимание: при помощи детерминистского протокола включает в себя, что направление каждого следующего бита - от кого к кому - строго определено содержимым канала до сих пор. Например, можно как бы решить задачу за n+1 бит следующим образом: Алиса посылает свое число бит за битом, начиная с верхнего; как только Боб видит расхождение со своим числом, он тут же отвечает "1" или "0" в зависимости от того, бит Алисы больше бита Боба или меньше, и после этого соответственно либо Алиса, либо Боб посылают в обратную сторону остаток своего числа. Но это недетерминистский алгоритм, потому что после каждого бита Алисы мы не знаем, кто посылает следующим: Алиса свой очередной бит, или Боб свой ответ: они соревнуются друг с другом за один и тот же канал. Условие задачи этого не позволяет.

Учитывая эти ограничения, сколько бит должны потратить Алиса и Боб? Например, тривиально это сделать за 2n бит: Алиса посылает свое число Бобу, Боб отвечает своим числом, и оба знают ответ. Но можно ли затратить меньше? Известны нижние и верхние пределы.

Нижний предел. Легко доказать, что за меньше чем n бит не справиться (оставляю это в качестве упражнения для читателя).

Верхний предел, лучший из известных, равен n+O(log(n)) бит (на самом деле чуть меньше). Я сначала объясню, как решить задачу за n+O(sqrt(n)) - это довольно просто - а потом объясню красивый трюк, который позволяет добиться n+O(log(n)).

Может, вы можете сблизить пределы - либо поднять нижний, либо найти еще более хитрый алгоритм и опустить верхний? Если вам это удастся, то сообщите Биллу Гасарчу (ну и мне тоже интересно, конечно).

Итак, алгоритм. Пусть Алиса посылает раз за разом блок из k бит своего числа (начиная с верхних), а Боб отвечает ей так: либо 0 - "у меня пока так же", либо 1 "на этих k битах расхождение", и тогда сразу еще один бит: либо 0 - "у меня больше", либо 1 - "у меня меньше". Если Боб отвечает 10 ("расхождение + у меня больше"), то сразу после этого он также посылает весь остаток своего числа начиная с этого блока и до конца; если отвечает 11, то Алиса после получения посылает весь остаток своего числа, уже не ожидая никаких подтверждений.
Сколько бит мы всего затрачиваем поверх n бит самого числа? Если A и B одинаковые, то дополнительные биты - только ответы B на каждый блок, так что всего затрачено n+n/k бит (n/k - количество блоков); если разные, и расхождение нашлось на m-ном блоке, то всего бит затрачено то ли n+m+1, то ли n+m+1+k (m+1 - биты ответов Боба; k затрачено, если Боб отвечает 10 и должен заново передать m-ный блок). Значит, если выбрать размер блока k=sqrt(n), так что n/k = sqrt(n), и m <= sqrt(n), то всего количество бит будет точно не больше n+2sqrt(n) + O(1). В худшем случае мы потеряем sqrt(n) бит на подтверждения одинаковых блоков почти до самого конца числа, и еще sqrt(n) бит на то, что Боб передаст последний блок Алисе, после того, как она ему уже послала свой последний блок.

Этот результат можно улучшить до n+sqrt(2n)+O(1) (главная разница во втором члене: sqrt(2n) по сравнению с 2sqrt(n)). Будем каждый раз уменьшать размер блока на один бит: k, k-1, k-2... Тогда в случае расхождения Бобу надо передать заново всего k-i бит, а не k, и это хорошо суммируется с i бит-подтверждений, которые он передавал до того. Зато количество блоков растет. Если выбрать начальный размер блока k = sqrt(2n), то после sqrt(2n) блоков, несмотря на постепенное уменьшение размера блока, мы передадим все число (оставляю точный подсчет заинтересованному читателю); а если в какой-то момент будет расхождение, то i подтверждений до него и k-i бит на передачу заново этого блока после вместе тоже дают sqrt(2n). Так что общее количество затраченных бит равно n+sqrt(2n)+O(1).

Как добиться еще лучшего результата? Основная проблема, "съедающая" биты - необходимость отвечать на каждый блок. Даже если мы тратим (обычно) один бит ответа на блок, то получается tradeoff между количеством блоков (по биту на каждый) и размером блока (один блок, возможно, надо заново передать). Как избавиться от этого? Один красивый прием достигает лучшего результата, маскируя подтверждающие биты под обычные биты числа. Вот как это делается.

Будем опять считать, что мы передаем блок из k бит за раз, где k постоянно; но теперь Алиса и Боб посылают попеременно: сначала Алиса первые k бит, потом Боб вторые k бит, и так далее. Но нам все равно нужно как-то обозначить расхождение, потому что после расхождения необходимо, чтобы только один из участников передавал все остальные биты - иначе слишком дорого выходит.

Предположим, что Алиса и Боб могут заранее найти такие куски из k бит, которые не встречаются в качестве "обычных" блоков в их числах. Алиса находит такой кусок A', и посылает его Бобу; Боб находит такой кусок B', и посылает его Алисе. Теперь Алиса знает, что если она получает кусок B', то это не обычный следующий блок из k бит от Боба, а "сигнальный" блок; и то же самое Боб знает о A'. Теперь они начинают обмениваться обычными блоками, пока один из них не видит расхождение между тем, что получил, и своим числом; тогда этот участник посылает свой "сигнальный" блок, а после него 1 или 0 в зависимости от того, расхождение в его пользу или нет. Затем либо он, либо другой участник посылают остаток числа (текущий блок из k бит, возможно, надо переслать заново). Сколько всего затрачено дополнительных бит? 2k на начальный обмен A'/B', еще k на сигнальный блок, и еще k на передачу заново (возможно) текущего блока; всего n+4k+O(1). Но мы не можем выбрать k очень малым: что если k так мало, что в исходном числе A есть все возможные комбинации из k бит в виде обычных блоков? - тогда мы не сможем подобрать A' и алгоритм не сработает. Возможных комбинаций есть 2^k, а число блоков равно n/k. Значит, условие на k выглядит так: 2^k > n/k. Если подставить k = log(n), то это условие выполняется; значит, этот алгоритм дает нам n+O(log(n))+O(1) бит. Можно даже взять k чуть меньше, чем log(n) и все еще соблюсти условие: например, k = log(n)-log(log(n)-log(log(n))) выполняет нужное условие.

Есть другое решение за n+O(log(n))+O(1) бит, которое использует другой трюк, и в итоге требует лишь 2*log(n) дополнительных бит, не считая O(1) (решение выше требует 4*log(n)). Это решение основано на том, что исходное число из алфавита {0,1} перекодируется в другой алфавит таким образом, чтобы внутри каждого блока оставалось место для подтверждающих битов. Оно описано в этой недавней статье (appendix B, Lemma 1).
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 26 comments