Является ли эта вариация TQBF все еще PSPACE-полной?

31

Решение, если количественная логическая формула, такая как

Икс1Икс2Икс3ИксNφ(Икс1,Икс2,...,ИксN),

всегда оценивается как истина - это классическая PSPACE-полная проблема. Это можно рассматривать как игру двух игроков с чередующимися ходами. Первый игрок решает значение истинности переменных с нечетными номерами, а второй игрок решает значение истинности переменных с четными номерами. Первый игрок пытается сделать ложным, а второй игрок пытается сделать это правдой. Решение о том, кто имеет выигрышную стратегию, полностью завершено.φ

Я рассматриваю аналогичную проблему с двумя игроками, один пытается сделать булеву формулу истинной, а другой - ложной. Разница в том, что на ходу игрок может выбрать для него переменную и значение истины (например, в самом первом ходу игрок 1 может решить установить значение в true, а затем в следующем ходу игрок 2 может решить установить в false). Это означает, что игроки могут решить, какие из переменных (из тех, которым еще не было назначено значение истинности) они хотят назначить значение истинности, вместо того, чтобы играть в игру в порядке .φИкс8Икс3Икс1,...,ИксN

Задача задается булевой формулой для переменных, чтобы решить, имеет ли первый игрок (пытающийся сделать его ложным) или второй (пытающийся сделать это правдивым) выигрышную стратегию. Эта проблема явно осталась в PSPACE, поскольку дерево игр имеет линейную глубину.φN

Остаётся ли PSPACE завершенным?

JWM
источник

Ответы:

35

Это игра « Неупорядоченное удовлетворение ограничений», она PSPACE-завершена и доказана, что PSPACE-полная только недавно ; доказательство можно найти в:

Лаури Алрот и Пекка Орпонен, Игры с неупорядоченным ограничением . Конспект лекций в области компьютерных наук, том 7464, 2012, с. 64-75.

Аннотация:Мы рассматриваем игры для удовлетворения ограничений двух игроков на системах логических ограничений, в которых игроки по очереди выбирают одну из доступных переменных и устанавливают ее в значение true или false с целью максимизации (для игрока I) или минимизации (для игрока). II) количество выполненных ограничений. В отличие от стандартных игр с присвоением переменных типа QBF, мы не навязываем порядок, в котором переменные должны проигрываться. Это делает настройку игры более естественной, но и более сложной для управления. Мы предоставляем стратегии аппроксимации с постоянным множителем за полиномиальное время для Игрока I, когда ограничения представляют собой функции четности или пороговые функции с небольшим порогом по сравнению с арностью ограничений. Кроме того, мы доказываем, что проблема определения того, может ли Player I удовлетворить все ограничения, является PSPACE-полной даже в этой неупорядоченной настройке,

Из содержания:

...
Наш общий пример неупорядоченной игры для удовлетворения ограничений - это игра по булевым формулам ( GBF ). Экземпляр этой игры задаются набором м неконстантных булевых формул над общим набором п переменных Х = { х 1 , . , , , х н } . Мы ссылаемся на формулы в C как на предложения, хотя в общем случае мы не требуем, чтобы они были дизъюнкциями. ...Сзнак равно{с1,,,,,см}Иксзнак равно{Икс1,,,,,ИксN}С

Игра на продолжается таким образом, что каждый ход игрока выбирает одну из ранее не выбранных переменных и присваивает ей значение истинности. Игрок I запускается, и игра заканчивается, когда всем переменным присвоено значение. В версии GBF для принятия решения вопрос заключается в том, имеет ли Игрок I всеобъемлющую выигрышную стратегию, с помощью которой она может выполнить все условия независимо от того, что делает Игрок II. В положительном случае мы говорим, что экземпляр является GBF-удовлетворяемым. ..С

... Теорема 4. Задача определения GBF-выполнимости булевой формулы является PSPACE-полной.

РЕДАКТИРОВАТЬ : Даниэль Гриер узнал, что результат был также достигнут Шефером в 70-х, см. Его ответ на этой странице для справки (и upvote его :-). Шефер доказал, что игра все еще PSPACE-полная, даже если она ограничена положительными формулами CNF (т. Е. Пропозициональными формулами в конъюнктивной нормальной форме, в которой нет отрицательных переменных) с максимум 11 переменными в каждом соединении.

Марцио де Биаси
источник
27

Также стоит отметить, что эта проблема была также решена в 70-х годах Томасом Шефером в « Сложности решения задач на основе конечных игр с идеальной информацией от двух человек» . Фактически, он доказывает немного более сильный результат в том, что язык остается PSPACE-полным, даже если он ограничен положительными формулами CNF.

Даниэль Гриер
источник
2
Интересный! (Альрот и Орпонен этого не знали? Кстати, они цитируют еще одну статью Шефера: «О сложности некоторых игр с совершенной информацией для двоих» (1978), в которой содержатся хорошо известные результаты полноты PSPACE по географии и Node-Kayles). Есть ли бесплатная копия бумаги? (связанный вне платного доступа).
Марцио Де Биаси,
К сожалению, я так не думаю. Я помню, как однажды пытался найти копию, которая некоторое время не стояла за платным экраном, но без особого успеха.
Даниэль Гриер
Кстати, поздравляю вас с отличным результатом по PSPACE-полноте Poset Games!
Марцио Де Биаси
Насколько я могу судить, статья 1978 года (О сложности некоторых из двух человек ...) является журнальной версией статьи STOC 1976 года (Сложность решения проблем ...), на которую она ссылается.
Андрас Саламон
10

Мы доказали, что эта игра является PSPACE-полной для 5-CNF, но имеет алгоритм линейного времени для 2-CNF. Предыдущий лучший результат был 6-CNF Ahlroth и Orponen.

Вы можете найти документ конференции на ISAAC 2018 .

Обновление: 16 ноября 2019 г.

Мы доказали, что игра доступна для 3-CNF с некоторыми ограничениями для 3-CNF. Мы также радикально предположили, что эта игра также доступна без ограничений для 3-CNF. Вы можете найти первоначальную версию на ECCC .

Лутфар Рахман Милу
источник