Вопросы с тегом «pspace»

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

Решение, если количественная логическая формула, такая как ∀ х1∃ х2∀ х3⋯ ∃ хNφ ( х1, х2, … , ХN) ,∀Икс1∃Икс2∀Икс3⋯∃ИксNφ(Икс1,Икс2,...,ИксN),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), всегда оценивается как истина - это классическая PSPACE-полная проблема....

21
Для каких регулярных выражений

Хорошо известно, что следующая проблема является PSPACE-полной: Учитывая регулярное выражение , ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ*L(β)=Σ∗L(\beta) = \Sigma^* Как насчет определения эквивалентности другим (фиксированным) регулярным выражениям ?αα\alpha Учитывая регулярное выражение , ?L ( β ) = L ( α...

17
Что такое оракул минимальной сложности, который отделяет PSPACE от полиномиальной иерархии?

Фон Известно , что существует оракул такое , что .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Даже известно, что разделение справедливо относительно случайного оракула. Неофициально можно интерпретировать это как означающее, что существует много оракулов, для которых и...

14
Означает ли PSPACE-полнота твердость аппроксимации?

В другом посте cstheorySE упоминается, что PSPACE-полнота подразумевает APX-жесткость. Кто-нибудь может объяснить / поделиться ссылкой на это? Это "плотно"? (т. е. существуют ли PSPACE-полные задачи, задача оптимизации которых допускает постоянную аппроксимацию множителя за много времени?) Как...

12
Есть ли сокращение до игр «дверь и прижимная пластина», которые не увеличивают длину решения?

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

12
Были ли решены эти раскраски?

В статье «О сложности некоторых раскрасок» Бодлендер дает несколько открытых вопросов о сложности решения, имеет ли игрок 1 или 2 выигрышную стратегию в некоторых играх раскраски графов. Кто-нибудь знает, были ли они решены? 1) В одной игре два игрока по очереди выбирают одну вершину на графике и...

11
Какова сложность подсчета числа решений задачи P-Space Complete? Как насчет классов повышенной сложности?

Я предполагаю, что это назвали бы # P-Space, но я нашел только одну статью, смутно упоминающую это. Как насчет подсчета версий EXP-TIME-Complete, NEXP-Complete, а также проблем EXP-SPACE-Complete? Есть ли какие-либо предыдущие работы, которые можно привести в отношении этого или любого типа...

11
Есть ли простая игра с асимметричной сложностью?

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