Предположим структуру в сложности коммуникации, где у нас есть два игрока A (вши) и B (ob) и R (eferee). А и Б не общаются напрямую друг с другом. В каждом раунде общения каждый из них отправляет сообщение (, ) в R.R вычисляет две функции а также и отправляет результаты им. Функции фиксированы. Идея в том, что общение между игроками ограничено. Кроме того, судья может выполнить некоторую обработку сообщений.
Пример:
A и B отправляют два (произвольно больших) числа в R, R проверяет, какое из них больше, и информирует игроков.
В этой структуре мы можем разработать простой протокол, который легко вычисляет следующую функцию, используя один раунд. А и Б отправить а также для R, R возвращает ответ им, и они выводят ответ.
Очевидно, это не интересный случай, так как вычисляемая нами функция совпадает с функциями рефери. Более интересный случай, когда мы имеем фиксированное линейное неравенство и значения для переменных разделены между игроками (А имеет и Б имеет ). Задача состоит в том, чтобы решить, является ли неравенство правильным. Протокол в этом случае состоит в том, что игроки вычисляют свою часть, а затем отправляют их рефери.
Вопрос:
Был ли изучен этот вид сложности общения? Если да, где я могу найти больше об этом?
примечание 1: на стр. 49 Кушилевиц и Нисан упоминают структуру, в которой участвует рефери, но, похоже, она сильно отличается от того, что я спрашиваю.
примечание 2: я не уверен, что называть R рефери - правильная вещь, пожалуйста, прокомментируйте, если у вас есть лучшее предложение.
Ответы:
Я уверен, что вы знаете следующую статью, но я поместил ссылку на нее, потому что другие читатели могут быть заинтересованы: Интерполяция по играм
Эта статья является попыткой использовать структуру сложности связи, чтобы показать нижние границы для резки плоскостей. Протокол используется для создания интерполяционной схемы для неудовлетворительного CNF:
игрокA получает вход a а также ya , игрок B получает b а также zb , Если в срезанных плоскостях есть мелкое древовидное доказательство, то у двух игроков есть протокол связи, такой что
Рефери превращается в вероятностный протокол о неравенствах. Таким образом, можно превратить нижнюю границу для древовидных вероятностных протоколов в структуре сложности связи в нижнюю границу для древовидных доказательств разрезающих плоскостей.
Если бы у нас была нижняя граница для протокола связи в форме PLS, то мы получили бы нижнюю границу для доказательств в виде дагоподобных плоскостей резания.
Обратите внимание, что этот метод не зависит от фактических правил вывода плоскостей резания. Если мы предположим, что правила вывода равны (1) положительной комбинации (2) целочисленное деление с полом, мы можем построить монотонную интерполированную схему, используя аргумент Павла Пудлака .
источник
Просто несколько замечаний. Во-первых, я не совсем понимаю, зачем вообще нужен судья. Если его / ее функция известна игрокам, то почему они не могут просто симулировать рефери? Алиса отправляетmA Бобу, он (не видя mA ) вычисляет
mB после этого он вычисляет f(mA,mB) и сообщает результат Алисе. Возможно, вы предполагаете, чтоfA это не известно Бобу, иfB Алисе?
Во-вторых, протоколы, связанные с линейными неравенствами, действительно интересны в контексте доказательства плоских разрезов. В этом случае даже достаточно рассмотреть протоколы, где форма сообщений очень ограничена : могут передаваться только значения некоторых линейных комбинаций входных переменных.
Чтобы быть более точным, предположим, что нам дана система линейных неравенств с целыми коэффициентами. Мы знаем, что система не имеет0 -1 решение. Переменные так или иначе поделены между игроками (в пропорции пятьдесят на пятьдесят); это сценарий «худшего раздела»: противник может выбрать «худший» раздел. Учитывая0 -1 Строка, цель игроков - найти неудовлетворенное неравенство. То есть ответ теперь не один бит, а название одного неравенства нашей системы. (Это коммуникационная игра типа Карчмера-Вигдерсона.)
Теперь рассмотрим следующие ограниченные протоколы для такой игры: (i) функция рефери, если толькоf(α,β)=1 тогда и только тогда α≤β (ii) сообщения игроков ограничены линейными : в каждом раунде Алиса должна отправлять сообщение в формеmA(x⃗ )=c⃗ ⋅x⃗ и Бобу сообщение в форме mB(y⃗ )=d⃗ ⋅y⃗ ,
Impagliazzo, Pitassi и Urquhart (1994) наблюдали следующее: если все коэффициенты, использованные в доказательствах плоскости разреза, являются полиномиальными по числу переменных, и если эта игра нуждаетсяt битов связи, то каждое древовидное доказательство неудовлетворенности данной системы должно давать exp(t/logn) неравенства. Затем они использовали известные нижние оценки сложности связи, чтобы дать явную систему, требующую доказательств экспоненциального размера. Недостаток этого результата в том, что система очень искусственная , она не соответствует «реальной» задаче оптимизации. Поэтому интересно поставить нижнюю оценку для «реальных» задач оптимизации.
Одной из таких проблем является проблема независимых множеств для графов. Учитывая графикG=(V,E) мы можем связать с каждой вершиной u Переменная xu и рассмотрим систему неравенств, состоящую из неравенства
∑v∈Vxv>α(G) и все неравенства xu+xv≤1 для всех краев uv из G , Так как каждый0 -1 Решение для подсистемы этих последних неравенств дает независимое множество в G вся система не имеет нулевых решений. Какова коммуникационная сложность игр для таких систем?
Если наш график=(L∪R,E)
является двудольным, то естественно (для противника) разделить переменные по частям. В этом случае Алиса получает подмножествоA⊆L Боб подмножество B⊆R
с обещанием, что |A∪B|>α(G) , Цель состоит в том, чтобы найти грань между
A а также B , Вотα(G) является «двудольным» числом независимости: максимальный размер независимого множества, не лежащего полностью в L или в R , Одна из моих любимых проблем: докажи, чтоn×n графики, требующие ω(log2n) биты общения существуют .
@Kaveh: Извините за «ответ» на ваш вопрос с вопросами.
источник