Рассмотрим следующую игру на ориентированном взвешенном графе с чипом в некотором узле.
Все узлы отмечены буквой A или B.
Есть два игрока Алиса и Боб. Цель Алисы (Боба) - сдвинуть фишку к узлу, обозначенному буквой A (B).
Первоначально Алиса и Боб имеют и долларов соответственно.
Если игрок находится в проигрышной позиции (то есть текущая позиция фишки помечена противоположной буквой), он или она может переместить фишку в соседний узел. Такой ход стоит несколько долларов (вес соответствующего ребра).
Игрок проигрывает, если он или она находится в проигрышной позиции и не имеет денег, чтобы это исправить.
Теперь рассмотрим язык GAME, который состоит из всех ориентированных взвешенных графов (все веса являются положительными целыми числами), начальной позиции фишки и прописных букв Алисы и Боба, указанных в унарном представлении.
такой, что у Алисы есть выигрышная стратегия в этой игре.
Язык GAME принадлежит P . Действительно, текущая позиция игры определяется позицией фишки и текущими столицами Алисы и Боба, поэтому динамическое программирование работает (здесь важно, чтобы начальные заглавные буквы были указаны в унарном представлении).
Теперь рассмотрим следующее обобщение этой игры. Рассмотрим несколько ориентированных взвешенных графов с чипом на каждом графе. Все узлы всех графиков помечены буквами A и B. Теперь Боб выигрывает, если все фишки помечены буквой B, а Алиса побеждает, если хотя бы одна фишка помечена буквой A.
Рассмотрим язык MULTI-GAME, который состоит из всех графов , начальных позиций и столиц и (в унарном представлении), так что Алиса выигрывает в соответствующей игре. Здесь важно, чтобы заглавные буквы были общими для всех графиков, поэтому речь идет не только о нескольких независимых ИГРАХ.
Вопрос В чем сложность языка MULTI-GAMES? (Это также относится к P или есть некоторые причины полагать, что эта проблема сложная?)
UPD1 Нил Янг предложил использовать теорию Конвея. Однако я не знаю, возможно ли использовать эту теорию для нескольких игр с общим капиталом.
UPD2 Я хочу показать пример, который показывает, что MULTI-GAME не очень прост. Пусть Алиса разделит свою столицу к некоторому точки (она собирается использовать я доллары я -му граф). Определим б я как минимальное число такоечто я -м игры Боб выигрываетесли Алиса и Боб имеют я и б я долларов соответственно. Если b 1 + … b (для некоторого разделения ) тогда Алиса побеждает. Однако обратное неверно. Рассмотрим две копии следующего графика (изначально чип находится слева вверху A):
Для одного графика Боб выигрывает, если и или если и . Однако для игры с двумя копиями этого графа Боб проигрывает, если и . Действительно, Боб придется потратить или долларов , чтобы сдвинуть обе фишки на узел , отмеченный . Затем Алиса может переместить хотя бы одну фишку в узел, помеченный буквой A. После этого у Боба нет денег, чтобы сохранить свою позицию.
UPD3 Так как вопрос для произвольных графов кажется трудным, рассмотрим конкретные графы. Обозначим узлы некоторого графа , как . Мое ограничение следующее: для каждой пары существует ребро от до и обратного ребра нет. Также существует ограничение на стоимость ребер: для ребро от до не больше, чем от до .
источник
Ответы:
Поскольку ответ Стивена Стадницкого, по-видимому, не был принят запрашивающим, я подумал, что все же может быть полезно предоставить обновление: у меня есть сокращение от 3SAT до MULTI-GAME. Я не внимательно изучил ответ Стивена и не проследовал по предоставленной им ссылке, но, основываясь на следующем сокращении, я не удивлюсь, если MULTI-GAME действительно PSPACE-завершена. Однако, возможно, я не стану расширять этот результат за пределы NP-твердости.
Экземпляр 3SAT состоит из пунктовC1,…,Cm , причем каждое предложение имеет вид Ci=Li1∨Li2∨Li3 где каждый Lik является одной из переменных x1,…,xn или отрицание одной из переменных.
Для такого экземпляра 3SAT сокращение создает экземпляр MULTI-GAME, состоящий изn+1 игр - по одной на каждую переменную, а другая игра используется в качестве поглотителя избыточного капитала. Сначала мы определим структуру графиков для каждой игры, затем рассмотрим пример и обсудим основную идею, а затем выясним, какие именно затраты следует назначить ребрам, чтобы сделать сокращение устойчивым.
Сначала переменный игровой графGj для каждой переменной xj :
Для каждого литералаLik предложения Ci , если Lik=xj или Lik=¬xj , создайте вершины с меткой CiTA и CiFA помеченные A, и вершины, помеченные CiTB и CiFB помеченный буквой B. Добавьте ребра (T,CiTA) и(F,CiFA) с затратами, установленными вlik . (Мы определимlik позже.)
Добавьте ребра(CiTA,CiTB) и (CiTA,CiTB) . Если Lik=xj , то установите стоимость ( C i T A , C i T B ) равной l i k - 1 и ( C i T A , C i T B ) , то стоимость l i k . В противном случае установите ( C i T A , C i T B )(CiTA,CiTB) lik−1 (CiTA,CiTB) lik (CiTA,CiTB) равной lik а стоимость (CiTA,CiTB) равной lik−1 .
Столичная раковина игры:
Это много, чтобы принять, так что, надеюсь, пример делает это немного более усваиваемым. Наш экземпляр 3SAT выглядит следующим образом:
Сокращение превращает этот экземпляр в 4 переменных игровых графа и 1 граф поглощения капитала. На диаграммах ниже красные вершины отмечены буквой A (т. Е. Являются выигрышными позициями для Алисы), а голубые вершины отмечены буквой B (это выигрышные позиции для Боба).
График дляx1 :
График дляx2 :
График для капитального стока:
Идея заключается в следующем:
(Ci?A CiTA CiFA
Если открытие Боба удовлетворяет всем условиям, мы можем поспорить об ограничениях параметров Алисы, которые исключают любую другую возможность победы Алисы. Обратите внимание, что порядок, в котором Алиса делает свои ходы, не имеет значения, поскольку ответы Боба являются вынужденными, и общий капитал, который Бобу потребуется для ответа на ходы Алисы, не изменяется в соответствии с порядком ходов Алисы.
Замечание к моему предыдущему ответу: задним числом очевидно, что для варианта MULTI-GAME, описанного в TABLE-GAME, который я определил в комментариях к этому ответу, DP в виде рюкзака достаточно, чтобы определить, какой игрок имеет выигрышную стратегию. Вы можете утверждать, что лучшая стратегия Боба - всегда реагировать на проигрышное состояние в данном игровом столе с минимально возможными инвестициями (это не может отрезать последующий ход для Боба, который он имел бы в противном случае), и оттуда, что заказ ходов Алисы не имеет значения. Затем возникает вопрос выбора доли капитала Алисы между играми таким образом, чтобы сумма минимальных выигрышных ответов Боба над этими играми превышала его бюджет, что можно переосмыслить как проблему типа рюкзака, которая имеет DP за полиномиальное время из-за до одинарного представления затрат. (Мой рецидив на самом деле будет
Я не особо задумывался о вашем особом случае с UPD3 . Я подозреваю, что это также NP-hard, потому что мои переменные гаджеты с первого взгляда кажутся такими, что они могут быть адаптированы к этим ограничениям, но я, вероятно, не буду вдаваться в подробности.
источник
Обновление: скорее всего, неверное, оставив на данный момент запись о том, что исследовали проспект. Смотрите комментарии.
Обновление 2: определенно неверно.
предвычисления
а также
источник
источник