Problemy z EXPSPACE

Obecnie próbuję znaleźć problemy pełne EXPSPACE (głównie w celu znalezienia inspiracji do redukcji) i jestem zaskoczony małą liczbą nadchodzących wyników.

Jak dotąd je znalazłem i mam problem z rozwinięciem listy:

• uniwersalność (lub inne właściwości) wyrażeń regularnych z potęgowaniem.
• problemy związane z systemami dodawania wektorów
• nieobserwowalne gry (patrz na przykład ten blog )
• jakiś fragment FO-LTL, w: O złożoności obliczeniowej rozstrzygalnych fragmentów logiki czasowej pierwszego rzędu

Czy znasz inne konteksty, gdy kompletność EXPSPACE pojawia się naturalnie?

Rozszerzając przykład wskazany przez Emila Jerabka w komentarzach, problemy kompletne pojawiają się naturalnie w całej geometrii algebraicznej. Zaczęło się to (jak sądzę) od Idealnego Problemu Członkostwa ( Mayr – Meyer i Mayr ), a stąd obliczenia baz Gröbnera. Zostało to następnie rozszerzone na obliczenia syzygii ( Bayer i Stillman ). Wiele naturalnych problemów obliczeniowej geometrii algebraicznej kończy się jako równoważnych z jednym z tych problemów. Zobacz także badanie Bayera – Mumforda „Co można obliczyć w geometrii algebraicznej?”$\mathsf{EXPSPACE}$

Wiele problemów, które są kompletne dla PSPACE, stają się kompletne dla EXPSPACE, gdy dane wejściowe są podawane „zwięźle”, tj. Poprzez pewne kodowanie, które pozwala opisać dane wejściowe, które normalnie miałyby rozmiar wykładniczy.

Oto przykład automatów skończonych (równoważnie na ukierunkowanych wykresach z etykietowanymi krawędziami): decyzja, czy dwa automaty akceptują ten sam język (mają ten sam zestaw ścieżek oznaczonych od źródła do węzła docelowego) jest kompletna z PSPACE. Jeśli automaty (wykresy) są podawane przez formuły boolowskie (węzły są wartościami v, v ', .. i istnieją formuły boolowskie mówiące, czy va-> v' jest krawędzią), problem staje się EXPSPACE-complete. Uwaga: istnieje wiele innych sposobów zwięzłego zdefiniowania dużego wykresu / automatu, patrz np. Ten artykuł .

Przykład z wyrażeniami regularnymi pasuje do tego wzorca. Wprowadzenie notacji „.. ^ 2” do kwadratu pozwala pisać zwarte wyrażenia regularne, które byłyby bardzo duże, gdybyśmy rozszerzyli każde „(foo) ^ 2” o „foo foo” i „((bar) ^ 2) ^ 2 ”przez„ bar bar bar bar ”. Oczywiście niektóre problemy, które są pełne PSPACE bez kwadratu, stają się EXPSPACE z dopuszczalnym kwadratem, oto klasyczne odniesienie . [Uwaga: inne przykłady, takie jak wyrażenia regularne ze skrzyżowaniem lub uzupełnieniami, oczywiście nie pasują do wzorca nowej notacji, która rozwija się w wykładniczo większy wkład w notacji standardowej.]

Podobnie problem z całkowitym LOGSPACE (np. Osiągalność w grafach ukierunkowanych) może stać się EXPSPACE-zupełny, jeśli twoje zwięzłe kodowanie pozwala na opisanie wykresów o podwójnie wykładniczym rozmiarze.

Podsumowując: możesz łatwo wymyślić nowe, choć być może sztuczne, problemy z EXPSPACE, biorąc pod uwagę klasyczne problemy PSPACE lub LOGSPACE (których jest wiele) i pozwalając na kompaktowe / zwięzłe kodowanie danych wejściowych.

Planowanie czasowe z jednoczesnymi działaniami jest zakończone EXPSPACE, jak pokazano w

J. Rintanen, „Złożoność jednoczesnego planowania czasowego”, Materiały z 17. Międzynarodowej Konferencji na temat Zautomatyzowanego Planowania i Planowania, str. 280–287, 2007

Problem jest mniej więcej następujący (uwaga w powyższym dokumencie jest zdefiniowana w inny, ale równoważny sposób). Niech będzie skończonym zbiorem zmiennych zdań, a O skończonym zbiorem działań , gdzie każde działanie to o = ( d , P s , P e , P o , E s , E e ) , gdzie:$A$$O$$o=(d,P_s,P_e,P_o,E_s,E_e)$

• oznacza czas trwania akcji.$d\in\mathbb{N}$
• $P_s$$P_e$$P_o$$A$
• $E_s$$E_e$$A$

$I$$G$$I$$G$

$d$

Większość standardowych klas z PSPACE na (cóż, nawet dla NP, jeśli chcesz) ma jakiś problem z kafelkami jako kompletny problem. Takie problemy z układaniem płytek nie są tak dalekie od kompletnych problemów opartych na naturalnej maszynie Turinga, ale często są dość wygodne jako punkt wyjścia do redukcji. Mówiąc w skrócie, problem z kafelkami daje zestaw dozwolonych kafelków (czyli rodzajów kafelków, z których można użyć dowolnej liczby kafelków) i określa sposób ich łączenia, często przez zestaw H par dozwolonych poziomo kafelki i zestaw V dozwolonych pionowo typów. Ponadto można podać pierwszy kafelek i ostatni kafelek oraz, w zależności od faktycznej wersji i liczby wierszy i / lub kolumn, które powinna mieć kafelek. Algorytmicznym pytaniem jest, czy istnieje poprawne kafelkowanie, to znaczy przypisanie pozycji do kafelków, który spełnia wszystkie ograniczenia i ma płytkę początkową w lewym dolnym położeniu, a ostatnią płytkę w prawym górnym rogu. (Istnieje wiele odmian dokładnych definicji).

W danej klasie EXPSPACE możesz wybrać (co najmniej) dwie wersje:

• wykładanie szerokości korytarza wykładniczego, w którym podany jest parametr n, a pytanie brzmi, czy istnieje sąsiadowanie z 2 ^ n kolumnami i dowolną liczbą wierszy
• exp-times-exp gra w kafelki, w której, przy n, kafelki będą miały rozmiar 2 ^ n razy 2 ^ n, w których celem pierwszego gracza jest osiągnięcie prawidłowego kafelkowania, a drugi gracz stara się temu zapobiec.

Dokumenty, na które warto zwrócić uwagę, to - Bogdan S. Chlebus: „Domino-Tiling Games”. J. Comput. Syst. Sci. 32 (3): 374-392 (1986) - Peter van Emde Boas: „Wygoda przechylania”, w: Złożoność, teoria logiki i rekurencji, Notatki z wykładu z matematyki czystej i stosowanej, t. 187, 1997, s. 331–363.

przykład i dowód podano we wstępie do teorii automatów, języków i obliczeń Hopcroft / Ullman Thm13.16, że dowolny niedeterministyczny algorytm dla teorii pierwszego rzędu z dodatkiem jest NExpTime-trudny. dlatego przypuszczalnie jest również trudny do uzyskania NExpSpace, chyba że jakiś teoretyczny przełom udowodni, że można go rozwiązać „w ciasnej przestrzeni”, ale oczywiście pytanie to jest podobne (prawie identyczne?) do L = pP. (innymi słowy, wszystkie znane problemy trudne dla NExpTime są również podstawowymi kandydatami dla trudnych dla NExpSpace, a jeśli jakikolwiek okazałby się niemożliwy, prawdopodobnie oznaczałoby to przełomowe rozwiązanie długo otwartej separacji klas złożoności.) dowód pochodzi od Fischera, Rabina 1974, „Nadwykładnicza złożoność arytmetyki Presburger'a”, Złożoność obliczeń(Red. R. Karp). Materiały z sympozjum SIAM-AMS w matematyce stosowanej.