Сложность общения с судьей

9

Предположим структуру в сложности коммуникации, где у нас есть два игрока A (вши) и B (ob) и R (eferee). А и Б не общаются напрямую друг с другом. В каждом раунде общения каждый из них отправляет сообщение (mA, mB) в R.R вычисляет две функции fA(mA,mB) а также fB(mA,mB)и отправляет результаты им. Функции фиксированы. Идея в том, что общение между игроками ограничено. Кроме того, судья может выполнить некоторую обработку сообщений.

Пример:

A и B отправляют два (произвольно больших) числа в R, R проверяет, какое из них больше, и информирует игроков.

В этой структуре мы можем разработать простой протокол, который легко вычисляет следующую функцию, используя один раунд. А и Б отправитьx а также y для R, R возвращает ответ им, и они выводят ответ.

f(x,y)={0xy1ow

Очевидно, это не интересный случай, так как вычисляемая нами функция совпадает с функциями рефери. Более интересный случай, когда мы имеем фиксированное линейное неравенствоaxby и значения для переменных разделены между игроками (А имеет x и Б имеет y). Задача состоит в том, чтобы решить, является ли неравенство правильным. Протокол в этом случае состоит в том, что игроки вычисляют свою часть, а затем отправляют их рефери.

Вопрос:

Был ли изучен этот вид сложности общения? Если да, где я могу найти больше об этом?


примечание 1: на стр. 49 Кушилевиц и Нисан упоминают структуру, в которой участвует рефери, но, похоже, она сильно отличается от того, что я спрашиваю.

примечание 2: я не уверен, что называть R рефери - правильная вещь, пожалуйста, прокомментируйте, если у вас есть лучшее предложение.

Кава
источник
2
модель, которую вы упоминаете, называется «одновременная передача сообщений»
Маркос Вильягра
2
проверьте этот документ ( arxiv.org/abs/quant-ph/0102001 ) и его ссылки. В частности, проверьте работы Амбайниса, Ньюмана и Сегеды.
Маркос Вильягра
2
вот более свежая статья Рауля Джахина ieeexplore.ieee.org/xpl/…
Маркос Вильягра
1
@MarcosVillagra: SMP - это то же самое, что и Note 1 Каве, не так ли?
Алессандро Косентино
@ Marcos, спасибо, я проверю их, но, исходя из тезисов, мне кажется, что SMP отличается от того, что я описываю. (Я постараюсь придумать лучший пример, чтобы прояснить, что игроки используют R для общения, что может занять несколько раундов.) PS: Я думаю, было бы лучше, если бы вы опубликовали эти комментарии в качестве ответа.
Каве

Ответы:

7

Я уверен, что вы знаете следующую статью, но я поместил ссылку на нее, потому что другие читатели могут быть заинтересованы: Интерполяция по играм

Эта статья является попыткой использовать структуру сложности связи, чтобы показать нижние границы для резки плоскостей. Протокол используется для создания интерполяционной схемы для неудовлетворительного CNF:

A(x,y)B(x,z).

игрок A получает вход a а также ya, игрок B получает b а также zb, Если в срезанных плоскостях есть мелкое древовидное доказательство, то у двух игроков есть протокол связи, такой что

  • любое сообщение опосредовано судьей, что помогает оценить неравенства в доказательстве;
  • количество общения невелико (дерево мелкое);
  • оба игрока решают, какой из A или B фальсифицирована;
  • они находят позицию i в котором aibi,

Рефери превращается в вероятностный протокол о неравенствах. Таким образом, можно превратить нижнюю границу для древовидных вероятностных протоколов в структуре сложности связи в нижнюю границу для древовидных доказательств разрезающих плоскостей.

Если бы у нас была нижняя граница для протокола связи в форме PLS, то мы получили бы нижнюю границу для доказательств в виде дагоподобных плоскостей резания.

Обратите внимание, что этот метод не зависит от фактических правил вывода плоскостей резания. Если мы предположим, что правила вывода равны (1) положительной комбинации (2) целочисленное деление с полом, мы можем построить монотонную интерполированную схему, используя аргумент Павла Пудлака .

MassimoLauria
источник
На самом деле я пытался выяснить, было ли изучено что-то более общее, чем это, в сложности коммуникации, поэтому я не упомянул нижнюю границу сложности доказательства и выполнимую интерполяцию не для того, чтобы искажать ответы, но спасибо. :)
Каве
2
Да, я так и думал. Но другие читатели этого форума могут быть заинтересованы и могут заинтересоваться доказательствами сложности.
MassimoLauria
5

Просто несколько замечаний. Во-первых, я не совсем понимаю, зачем вообще нужен судья. Если его / ее функция известна игрокам, то почему они не могут просто симулировать рефери? Алиса отправляетmA Бобу, он (не видя mA) вычисляет mBпосле этого он вычисляет f(mA,mB)и сообщает результат Алисе. Возможно, вы предполагаете, чтоfAэто не известно Бобу, иfB Алисе?

Во-вторых, протоколы, связанные с линейными неравенствами, действительно интересны в контексте доказательства плоских разрезов. В этом случае даже достаточно рассмотреть протоколы, где форма сообщений очень ограничена : могут передаваться только значения некоторых линейных комбинаций входных переменных.

Чтобы быть более точным, предположим, что нам дана система линейных неравенств с целыми коэффициентами. Мы знаем, что система не имеет0-1решение. Переменные так или иначе поделены между игроками (в пропорции пятьдесят на пятьдесят); это сценарий «худшего раздела»: противник может выбрать «худший» раздел. Учитывая0-1Строка, цель игроков - найти неудовлетворенное неравенство. То есть ответ теперь не один бит, а название одного неравенства нашей системы. (Это коммуникационная игра типа Карчмера-Вигдерсона.)

Теперь рассмотрим следующие ограниченные протоколы для такой игры: (i) функция рефери, если только f(α,β)=1 тогда и только тогда αβ(ii) сообщения игроков ограничены линейными : в каждом раунде Алиса должна отправлять сообщение в формеmA(x)=cxи Бобу сообщение в форме mB(y)=dy,

Impagliazzo, Pitassi и Urquhart (1994) наблюдали следующее: если все коэффициенты, использованные в доказательствах плоскости разреза, являются полиномиальными по числу переменных, и если эта игра нуждаетсяt битов связи, то каждое древовидное доказательство неудовлетворенности данной системы должно давать exp(t/logn)неравенства. Затем они использовали известные нижние оценки сложности связи, чтобы дать явную систему, требующую доказательств экспоненциального размера. Недостаток этого результата в том, что система очень искусственная , она не соответствует «реальной» задаче оптимизации. Поэтому интересно поставить нижнюю оценку для «реальных» задач оптимизации.

Одной из таких проблем является проблема независимых множеств для графов. Учитывая график G=(V,E) мы можем связать с каждой вершиной u Переменная xu и рассмотрим систему неравенств, состоящую из неравенства vVxv>α(G)и все неравенства xu+xv1 для всех краев uv из G, Так как каждый0-1 Решение для подсистемы этих последних неравенств дает независимое множество в Gвся система не имеет нулевых решений. Какова коммуникационная сложность игр для таких систем?

Если наш график =(LR,E) является двудольным, то естественно (для противника) разделить переменные по частям. В этом случае Алиса получает подмножествоALБоб подмножество BR с обещанием, что |AB|>α(G), Цель состоит в том, чтобы найти грань между A а также B, Вотα(G) является «двудольным» числом независимости: максимальный размер независимого множества, не лежащего полностью в L или в R, Одна из моих любимых проблем: докажи, чтоn×n графики, требующие ω(log2n)биты общения существуют .

@Kaveh: Извините за «ответ» на ваш вопрос с вопросами.

Стасис
источник
Меня больше интересует общая структура cc, чем ее известные приложения для доказательства сложности. Функции, используемые рефери, известны (они зафиксированы, как я сказал). Есть ряд вопросов, почему я заинтересован в этой модели, но главное в том, как мы будем измерять объем общения. Если нас интересует общее количество передаваемых битов, то можно смоделировать протокол, как вы сказали. Но если мы хотим рассмотреть некоторые другие меры сложности, такие как количество раундов, то я думаю, что это другое. Например, в одном случае, который был использован в
Kaveh
Сложность доказательства каждый игрок посылает реальный номер рефери. Вещественное число может кодировать бесконечно много битов, поэтому, если вы хотите смоделировать это, мы должны отправить бесконечное количество битов, и если мы разрешаем это, мы можем просто отправить весь ввод, так что это становится неинтересным. Но подсчитывая количество раундов в рамках с рефери, мы получаем другую меру, которая может быть полезна (как в доказательстве Павла Пудлака).
Каве
@Kaveh: Да, разумно, какое общение мы считаем. Но в рамках резки самолетов нам не нужно заботиться об отправке реальных чисел. Просто предположим , что все коэффициент являются целыми числами отO(logn) двоичный размер (nколичество переменных). Даже этот (ограниченный) случай неясен при желании получить что-то для «реальных» задач оптимизации (например, Independent Set). Мне не нравится получать нижние оценки для "проблем монстра". Люди в сложности доказательства обычно удовлетворяются "монстрами". Но люди в теории оптимизации хотели бы видеть «реальные» нижние границы.
Стасис
это побочные вопросы, поскольку, как я сказал, я хочу узнать больше о типе сложности общения, который я описал в этом вопросе, и намеренно избегал связывать его со сложностью доказательства и интерполяциями. В постановке моего вопроса нет ничего связанного со сложностью доказательства.
Каве
1
@Kaveh: Если функция судьи будет известна игрокам, я не вижу разницы между этими «судейскими протоколами» и «нет судейских протоколов» (если, как я сказал, цифры невелики). Разница может возникнуть, если у нас будет только один раунд: игроки отправляют свои сообщения рефери, и он принимает окончательное решение. Кстати, в случаеk>2игроков, это известно как «одновременная передача сообщений». О "проблемах монстров". Здесь я думаю не о сложности схемы, а о проблемах, с которыми сталкивается теория оптимизации.
Стасис