Реферированные игры с некоррелированными полу-частными монетами

Я был (и до сих пор) действительно заинтересован в ответе на этот вопрос, потому что это интересный вариант сложности игр, который не был решен, поэтому я предложил вознаграждение. Я подумал, что исходный вопрос, скорее всего, слишком сложный, поэтому я опубликовал три связанных вопроса, которые также заслуживают награды. Никто не опубликовал никаких ответов до истечения срока действия награды. Позже я смог ответить на два связанных вопроса (вопросы 3 и 4, обсуждаемые ниже в моем первоначальном посте), показывая, что аппроксимация стоимости рецензируемых игр с коррелированными полу-частными монетами (определенными ниже) была завершена EXPTIME. Оригинальный вопрос до сих пор остается без ответа. Я также был бы заинтересован в любых результатах, помещающих связанные игры между PSPACE и EXPTIME в интересные классы сложности.

ОРИГИНАЛЬНАЯ ПОЧТА:

Этот вопрос был вдохновлен обсуждением шестнадцатеричного вопроса Итая . Реферативный игра это игра , где два вычислительно неограниченные игроки играют путем общения через полиномиальное время проверяющий , который может перевернуть частные монеты (таким образом, число витков и количество коммуникации также полиномиальное время ограниченно). В конце игры судья запускает алгоритм в P, чтобы определить, кто победит. Определение того, кто победит в такой игре (даже приблизительно), EXPTIME завершено. Если у вас есть публичные монеты и общение, такие игры есть в PSPACE. ( См. Фейдж и Киллиан, «Делать игры короткими». ) Мой вопрос касается границы между этими двумя результатами.

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

  По результатам рецензируемых игр аппроксимирующая вероятность того, что первый игрок выиграет, находится в EXPTIME, и это также явно PSPACE-hard. Что (если есть) это? Что-нибудь известно об этой проблеме?

Обратите внимание, что игрокам, возможно, придется использовать смешанные стратегии, так как вы можете играть в игры с матрицей с нулевой суммой (a la von Neumann) таким образом.

ДОБАВЛЕННЫЙ МАТЕРИАЛ:

$L$$x \in L$$\geq 2/3$$x \notin L$$\leq 1/3$

• $\subseteq$$\subseteq$

• Вопрос 3: Я также сильно подозреваю, что класс RGCSP (Реферид-игры с коррелированными полубриватными монетами) завершен EXPTIME, и я также готов отдать награду тому, кто это подтвердит. В RGCSP на первом этапе рефери дает двум игрокам коррелированные случайные величины (например, он может дать первому игроку точку в большой проективной плоскости, а второму игроку - линию, содержащую эту точку). После этого за полиномиальное количество раундов два игрока поочередно отправляют друг другу публичные сообщения разного размера. После того, как игра была сыграна, главный судья решает, кто победил. Какова сложность аппроксимации вероятности выигрыша для игрока 1?

• Вопрос 4: Наконец, у меня есть вопрос, который действительно может касаться криптографии и распределения вероятностей: позволяет ли дать возможность забывать передачу двум игрокам в рецензируемой игре с некоррелированными полу-частными монетами, позволяя им играть в произвольную рецензируемую игру с коррелированными монетами (или, в качестве альтернативы, он позволяет им играть в игру, определяя, кто из них выиграл EXPTIME)?

Я не могу ответить на свой первоначальный вопрос, но я могу ответить на вопрос 3 (и 4), который я добавил, когда предложил вознаграждение, потому что я думал, что первоначальный вопрос, вероятно, был слишком сложным. На самом деле у меня есть два доказательства вопроса 3.

$2/3$

======== Доказательство 1 ============

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

$r_1$$r_2$$r_i$$i$$=1$$2$$r_1$$r_2$, P2 может затем декодировать один из них, но P1 не может сказать, какой из P2 может декодировать. Это 1-2 забывчивых перевода. (Очевидно, что рефери также должен дать игрокам забывчивые раздаточные коробки, направленные в другую сторону, от P2 к P1.)

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

=========== Доказательство 2 ===========

$2^n$$t$$Q_t($$, \ldots,$$)$$p$$Q_t$$t$$Q_t$$Q_{t+1}$

Первое, что мы будем использовать, это то, что, даже с некоррелированными случайными монетами, судья может заставить игроков 1 и 2 выполнять битовое обязательство, заставляя их XOR данные, которые они хотят зафиксировать с помощью случайных монет. Таким образом, мы можем говорить о том, что P1 и P2 помещают вещи в запечатанные конверты.

$p_i$$\ell_i$$p_i$$\ell_i$$Q_{t}(p_i)$$Q_t(\ell_i)$$(p_i, \ell_i)$

$(p_i, \ell_i)$

$Q_t(p_i)$$Q_t(p_j)$${p}'_k$${\ell}'_k$на набор линий P2. Пусть на каждой фиктивной линии есть две точки. Если случится, что P1 даст правильное значение для одной фиктивной точки на линии и неправильное значение для другой фиктивной точки, то он проявит себя как лжец, поскольку у P2 нет способа дать значение для линии, которая является исправить для одной из двух точек P1 на нем, а не другой. Мы можем сделать аналогичный трюк, чтобы P2 отвечал последовательно. Затем остается только показать, что последний шаг доказательства Фейге-Килиана все еще работает. Это оказывается простым, хотя проработка деталей сделает этот ответ намного длиннее.