Problemy, o których wiadomo, że nie są kompletne z PSPACE

Jakie są problemy z następującymi właściwościami:

1) są ograniczeniem (prawdopodobnie dobrze znanych) problemów, które są kompletne z PSPACE;

2) wersje ograniczone są w PSPACE, ale jest to otwarty problem, jeśli są one kompletne (lub nawet jeśli są trudne w wersji NP).

Cztery przykłady z „puzzli i C.”:

• Złożoność 1x1 Godziny szczytu [1] (PSPACE-complete dla bloków o rozmiarze 2x1);
• [ ROZWIĄZANE ] Złożoność płaskiego tasowania metra [1] (PSPACE-complete nawet dla płaskich grafów, szkic papieru można pobrać tutaj );
• Złożoność Lunar-Lockout bez stałych bloków [1] (PSPACE-complete ze stałymi blokami);
• (nie tak znany) Złożoność (mojego) problemu z siecią przełączającą (jest to ograniczenie PSBiO-Complete Sokoban, NP-hard w przypadku niepłaskim, patrz to pytanie i odpowiedzi na temat cstheory ).

Jeśli masz wiele, pogrupuj je według tematów.

[1] Robert A. Hearn, Erik D. Demaine: Gry, łamigłówki i obliczenia. AK Peters 2009, ISBN 978-1-56881-322-6, s. I-IX, 1-237

$PSPACE$$NP$

http://arxiv.org/abs/1409.1530

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

Nie jestem pewien, czy to pasuje do twojego pojęcia ograniczenia, ale proszę bardzo.

„Problem minimalnego rozmiaru obwodu QBF-oracle”: biorąc pod uwagę tabelę prawdy funkcji boolowskiej i parametru k, czy istnieje obwód wielkości co najwyżej k obliczający funkcję na podstawie AND, OR, NOT i QBF? (Bramka QBF interpretuje swój ciąg wejściowy jako w pełni kwantyfikowaną boolowską formułę F, a wynikiem jest 1, jeśli F jest prawdą.)

Problem jest zdecydowanie związany z PSPACE, o którym wiadomo, że jest kompletny w ramach redukcji ZPP, ale nie jest znany z deterministycznych wielomianowych redukcji czasu. Prawdopodobnie nie jest to kompletne PSPACE pod ograniczeniami przestrzeni logicznej! Zobacz Allender, Holden i Kabanets .

Poniższy problem jest jakoś podwójnie zgodny z tym wymaganiem ...

$r$$r'$$L(r)\subseteq L(r')$$r$$\Sigma^*$

$L(r)=L(r')$

$r_1\cdots r_n$$r_i$$e=(w_1+\ldots+w_m)$$w_j$$e^*$$e^+$$e?$$e$$a(b+cd)(ab+cde+f)^*d?$

Ograniczanie łańcuchowych wyrażeń regularnych jest wciąż pełne dla PSPACE, ale równoważność wyrażeń regularnych łańcuchów jest niejasna (chociaż wiadomo, że jest twarda na CoNP i w PSPACE).

Nawiasem mówiąc, górna granica PSPACE łatwo podąża za tłumaczeniem wyrażeń na NFA i niedeterministycznym szukaniem przeciwnego przykładu: zgadnij ciąg liter po literze i śledź zestawy stanów, do których można dotrzeć w NFA.

gry z zaledwie 2 przyciskami i 2 drzwiami, w których wszystkie drzwi są początkowo zamknięte:

„Poziomy” są skończonymi podgrafami planarnej siatki .$\:$ Wierzchołki są identyfikowane jako jeden z [start, przycisk, pusty, drzwi, koniec]. $\:$ Każdy wierzchołek drzwi ma zestaw przycisków otwierających i zestaw przycisków zamykających. $\:$ K-drzwi to drzwi, które są kontrolowane za pomocą co najwyżej k przycisków, a a przycisk k to przycisk, który kontroluje co najwyżej k drzwi. $\:$ Ilekroć na wierzchołku przycisku można nacisnąć przycisk, który otwiera drzwi, dla których przycisk jest przyciskiem otwierającym, i zamyka drzwi, dla których przycisk jest przyciskiem zamykającym. $\:$Celem jest przejście od wierzchołka początkowego do wierzchołka końcowego bez wchodzenia na zamknięte drzwi.


Takie poziomy można wyraźnie rozwiązać w FPSPACE, a ich rozwiązanie jest trudne w FNPSPACE,
nawet gdy [każde drzwi mają dokładnie jeden przycisk otwierania i dokładnie jeden przycisk zamykania]
i [każdy przycisk otwiera dokładnie jedne drzwi i zamyka dokładnie jedne drzwi].
Z drugiej strony w tym dokumencie stwierdzono, że „Problemem otwartym jest to, czy gra z
2 przyciskami i 2 drzwiami jest trudna do gry w PSPACE, gdy wszystkie drzwi są początkowo zamknięte”.


Twardość FNPSPACE, gdy wszystkie drzwi są początkowo zamknięte, zostanie odzyskana, jeśli dokładnie jeden z każdego z warunków z poprzedniego akapitu zostanie zmieniony na jeden z następujących sposobów:

zezwól, aby drzwi miały 2 przyciski otwierania (oprócz 1 przycisku zamykania)
lub
pozwól przyciskom zamknąć 2 drzwi (oprócz otwarcia 1 drzwi)

.


Strona 10 z tego papieru pokazuje, że określenie wypłacalność jest NC1 -hard nawet bez guzików i
bez drzwi.$\:$W przeciwnym razie nie znam wyników twardości dla rozwiązywania poziomów z 2 przyciskami
i 2 drzwiami, gdy wszystkie drzwi są początkowo zamknięte (nawet bez dokładnie jednego z każdych warunków).