Проблемы, о которых известно, что они не являются PSPACE-полными

12

Какие проблемы со следующими свойствами:

1) они являются ограничением (возможно общеизвестных) проблем, которые являются PSPACE-полными;

2) ограниченные версии находятся в PSPACE, но это открытая проблема, если они завершены PSPACE (или даже если они NP-hard).

Четыре примера из "головоломки и С.":

  • Сложность 1x1 Rush Hour [1] (PSPACE-полная для блоков размером 2x1);
  • [ Решено ] Сложность плоского Subwu Shuffle [1] (PSPACE-полная, даже для плоских графиков, черновик статьи можно скачать здесь );
  • Сложность Lunar-Lockout без фиксированных блоков [1] (PSPACE-комплект с фиксированными блоками);
  • (не очень известный) Сложность (моей) проблемы с сетью коммутатора (это ограничение Sokoban, полного PSPACE, NP-hard в непланарном случае, см. этот раздел вопросов и ответов по этой теме ).

Если у вас их много, сгруппируйте их по темам.

[1] Роберт А. Хирн, Эрик Д. Демейн: Игры, головоломки и вычисления. AK Peters 2009, ISBN 978-1-56881-322-6, с. I-IX, 1-237

Марцио де Биаси
источник
1
Почти у каждой проблемы, полной PSPACE, есть много особых случаев, которые никто не удосужился изучить. Как вы определяете открытую проблему ?
РБ
@RB: «открытая проблема» - проблема, которая в настоящее время изучается (или изучалась, цитировалась несколько раз, ...), и исследователи считают, что было бы интересно решить (по крайней мере, сформировать границу задач, завершенных PSPACE). ... под сенью демона P vs PSPACE :-).
Марцио Де Биаси
1
TAUT - это ограниченная версия QBF, и это открытая проблема, будь то PSPACE- или NP-hard, поэтому она отвечает всем требованиям, но почему-то я не думаю, что это в правильном духе.
Эмиль Йержабек
@ EmilJeřábek: QBF, ограниченный конечным числом квантификаторов, может быть в духе (т. Е. PH против PSPACE) ... но это переход от «бесконечного к конечному»; Меня больше интересуют ограничения на конечные «структуры» проблемы.
Марцио де Биаси

Ответы:

12

Ретроградные шахматы. Это -полным , если вам разрешено иметь сколь угодно много царей и ни один из них не может быть под контролем в любое время. Если не разрешено ни одного (или только одного на игрока) короля, известно, что существуют позиции, которые требуют экспоненциальных ходов, но известно, что проблема только в том, что N P -hard.PSPACENP

http://arxiv.org/abs/1409.1530

/mathpro/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach

Том ван дер Занден
источник
11

Я не уверен, соответствует ли это вашему понятию ограничения, но здесь идет.

«Проблема минимального размера схемы QBF-оракула»: учитывая таблицу истинности булевой функции и параметра k, существует ли схема размера не более k, вычисляющая функцию на основе И, ИЛИ, НЕ и QBF? (Гейт QBF интерпретирует свою входную строку как полностью количественную булеву формулу F, и вывод равен 1, если F истинно.)

Проблема определенно в PSPACE, которая, как известно, завершается при сокращениях ZPP, но не известна для детерминированных полиномиальных сокращений времени. По-видимому, не PSPACE-полный при сокращении пространства журналов! См. Аллендер, Холден и Кабанец .

Райан Уильямс
источник
7+o(1)
(Я должен был упомянуть об этом раньше, но) Теперь у меня есть вопрос о случае k = 7 на этом сайте.
5

Следующая проблема соответствует требованию как-то в два раза ...

rrL(r)L(r)rΣ

L(r)=L(r)

r1rnrie=(w1++wm)wjee+e?ea(b+cd)(ab+cde+f)d?

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

Кстати, верхняя граница PSPACE легко следует путем перевода выражений в NFA и недетерминированного поиска контрпримера: угадывайте строковую букву за буквой и отслеживайте наборы состояний, которые могут быть достигнуты в NFA.

Томас С
источник
2

игры с двумя кнопками и двумя дверями, в которых все двери изначально закрыты:

«Уровни» - это конечные подграфы плоской сетки . Вершины идентифицируются как одна из [начало, кнопка, пусто, дверь, конец]. Каждая вершина двери имеет набор открывающих кнопок и множество закрывающих кнопок. K-дверь - это дверь, которой управляют не более k кнопок, а k-кнопка - кнопка, которая управляет большинством k дверей. Всякий раз, когда на вершине кнопки, можно нажать кнопку, которая открывает двери, для которых кнопка является кнопкой открытия, и закрывает двери, для которых кнопка является кнопкой закрытия. Цель состоит в том, чтобы добраться от начальной вершины до конечной, не заходя в закрытые двери.


Такие уровни могут быть четко определены в FPSPACE, и их решение является сложным для FNPSPACE,
даже когда [каждая дверь имеет ровно одну кнопку открытия и ровно одну кнопку закрытия]
и [каждая кнопка открывает ровно одну дверь и закрывает ровно одну дверь].
С другой стороны, в этом документе говорится, что «остается открытой проблемой, остается ли игра с
2-мя кнопками и 2-мя дверями сложной для PSPACE, когда все двери изначально закрыты».


FNPSPACE-твердость, когда все двери первоначально закрыты, будет восстановлена, если условия «точно один из каждого» из моего предыдущего абзаца были изменены одним из следующих способов:

разрешить дверям иметь 2 кнопки открытия (в дополнение к 1 кнопке закрытия)
или
разрешить кнопкам закрыть 2 двери (в дополнение к открытию 1 двери)

,


Страница 10 из этой бумаги показывает , что определение разрешимости NC1 -трудной даже без каких - либо кнопок и
нет дверей.В противном случае, я не знаю каких-либо результатов твердости для решения уровней с 2 ​​кнопками
и 2 дверями, когда все двери изначально закрыты (даже без условий «один на каждый»).


источник
У вас есть простое доказательство или справка о твердости версии, противоположной знаку (где каждая кнопка открывает одну дверь и закрывает другую, а каждая дверь открывается одной кнопкой и закрывается другой)?
Йонас Кёлкер
Нет, хотя я понимаю, что знаю, как показать твердость, даже когда все двери начинают закрываться, что я, вероятно, опубликую в этом году.
Думаю, у меня есть идея, как это сделать. Вы отправите мне копию своей рукописи, когда получите ее? Я хотел бы сравнить идеи :-) [re: жесткость, противоположная знаку, IINM сокращение бумаги Bloxorz противоположно знаку как на дверях, так и на кнопках.]
Jonas Kölker,
Да.