Problemy z EXPSPACE


23

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:

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


2
Uważa się, że problem decyzyjny teorii prawdziwych zamkniętych pól jest EXPSPACE-complete w sciencedirect.com/science/article/pii/S0747717188800063 , chociaż mam trudności z ustaleniem, w jaki sposób część twardości powinna wynikać z podanego odniesienie ( sciencedirect.com/science/article/pii/0001870882900482 ). Arytmetyka Presburgera i teoria reali z dodatkiem są kompletne dla naprzemiennego czasu wykładniczego z wielomianowo wieloma przemianami (ze względu na Bermana), co jest bliskim brakiem (EXPSPACE jest taka sama bez ograniczeń alternatywnych).
Emil Jeřábek wspiera Monikę

6
W każdym razie, jakiej odpowiedzi na „czy naprawdę jest ich tak mało”, oczekujesz innych niż spekulowane spekulacje?
Emil Jeřábek wspiera Monikę

@ EmilJeřábek Głównie sprawdzam, czy nie zauważyłem niektórych z nich podczas wyszukiwania. Rzeczywiście, niektóre wydają się trudniejsze do znalezienia, jak ten, o którym wspomniałem w aktualizacji.
Denis

zgodzili się, że nie wydają się powszechne w literaturze, a także zgodzili się z EJ, że kwestia ich „rzadkości” nie jest bardzo dobrze zdefiniowana. możliwe, że nie są tak bardzo badane, ponieważ są trudne do zdefiniowania przez defn. podczas gdy np. z drugiej strony trudne / kompletne problemy NP nie są („jeszcze”) trudne do rozwiązania. (P vs NP)
dniu

pytanie nie brzmi „czy są rzadkie”, ale „czy możesz znaleźć innych niż te wymienione?” Zmienię, aby było jaśniej
Denis

Odpowiedzi:


22

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?”EXPSPACE


1
Idealny problem członkostwa jest również związany z problemem pokrycia w systemach dodawania wektorów , patrz Lipton (1976, cs.yale.edu/publications/techreports/tr63.pdf ) dla dolnej granicy i Rackoff (1978, dx.doi.org/ 10.1016 / 0304-3975 (78) 90036-1 ) dla górnej granicy.
Sylvain,

19

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.


Rzeczywiście, jest to rodzaj „oszukiwania”, szukam bardziej naturalnych. Przypadek pośredni występuje wtedy, gdy dane wejściowe zawierają tylko jedną liczbę całkowitą (jak PRIMES) i być może coś innego jak formułę, co mnie interesuje. W rzeczywistości pokazałem pełnię EXPSPACE dla takiego problemu, który jest granicą w opisywanej kategorii.
Denis

ponieważ jeśli masz liczbę całkowitą na wejściu, kodowanie jej w formacie binarnym jest najbardziej naturalnym sposobem, a nie pojedynczym, aby sztucznie zmniejszyć złożoność.
Denis

Bardziej niż „naturalny” problem, potrzebujesz takiego, który można łatwo zakodować w rodzaju redukcji, którą próbujesz osiągnąć. Zazwyczaj oznacza to „zbliżony do pierwotnego rozpatrywanego problemu”. Im więcej masz wyborów, tym większe prawdopodobieństwo, że znajdziesz coś całkiem bliskiego.
phs

5

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:AOo=(d,Ps,Pe,Po,Es,Ee)

  • oznacza czas trwania akcji.dN
  • PsPePoA
  • EsEeA

IGIG

d


5

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.


-8

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.


5
Pytanie dotyczy problemów kompletnych z EXPSPACE, a dostarczyłeś wielu problemów, które są trudne dla innych klas złożoności, które, jak się uważa, różnią się od EXPSPACE. Nawet nie wspominasz o EXPSPACE. Czemu?
David Richerby

jak powiedziano, kandydaci / badacze prowadzą, a także niektórzy powracają do pierwotnego pytania, dlaczego takie problemy mogą być „rzadkie”, ponieważ ich istnienie może być powiązane z otwartymi podziałami klas złożoności. dla każdego, kto szukał dowodów na problemy z NExpSpace-kompletne i NExpTime-twarde są bardzo podobne i interesujące byłoby wskazanie, dlaczego dowody NExpTime nie są wystarczające również dla kompletności właściwości NExpSpace (jeśli można to zrobić przy obecnej wiedzy)
vzn
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.