WYŚWIETLACZ - EXPSPACE

W teorii złożoności obliczeniowej , EXPSPACE jest zestaw wszystkich problemów decyzyjnych rozwiązany przez deterministycznej maszyny Turinga w wykładniczej przestrzeni , czyli w miejscu, gdzie jest wielomianem funkcją . Niektórzy autorzy ograniczają się do funkcji liniowej , ale większość autorów zamiast tego nazywa wynikową klasę ESPACE . Jeśli zamiast tego użyjemy maszyny niedeterministycznej, otrzymamy klasę NEXPSPACE , która jest równa EXPSPACE według twierdzenia Savitcha . ${\ Displaystyle O (2 ^ {p (n)})}$${\ Displaystyle p (n)}$${\ Displaystyle n}$${\ Displaystyle p (n)}$

Problem decyzyjny jest EXPSPACE-zupełny, jeśli znajduje się w EXPSPACE , a każdy problem w EXPSPACE ma redukcję wielomianową wiele-jeden . Innymi słowy, istnieje algorytm wielomianowy , który przekształca instancje jednego w instancje drugiego z tą samą odpowiedzią. Problemy z wypełnieniem EXPSPACE mogą być uważane za najtrudniejsze problemy w EXPSPACE .

EXPSPACE jest ścisłym nadzbiorem PSPACE , NP i P i uważa się , że jest ścisłym nadzbiorem EXPTIME .

Formalna definicja

W zakresie DSPACE i NSPACE ,

${\ Displaystyle {\ mathsf {EXPSPACE}} = \ bigcup _ {k \ w \ mathbb {N}} {\ mathsf {DSPACE}} \ lewo (2 ^ {n ^ {k}} \ po prawej) = \ bigcup _ {k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)}$

Przykłady problemów

Przykładem problemu EXPSPACE-complete jest problem rozpoznawania, czy dwa wyrażenia regularne reprezentują różne języki, gdzie wyrażenia są ograniczone do czterech operatorów: suma, konkatenacja , gwiazda Kleene (zero lub więcej kopii wyrażenia) i kwadrat ( dwie kopie wyrażenia).

Jeżeli gwiazda Kleene jest pominięty, to problem staje NEXPTIME -Complete , który jest jak EXPTIME-kompletne , oprócz tego, że jest definiowany w kategoriach non-deterministycznych maszyn Turinga , a nie deterministyczne.

L. Berman wykazał również w 1980 r., że problem weryfikacji/fałszowania dowolnego twierdzenia pierwszego rzędu o liczbach rzeczywistych, które obejmuje tylko dodawanie i porównywanie (ale nie mnożenie ) jest w EXPSPACE .

Alur i Henzinger rozszerzyli liniową logikę temporalną o czasy (liczby całkowite) i udowodnili, że problem ważności ich logiki jest zupełny EXPSPACE.

Problem pokrywalności dla sieci Petriego to EXPSPACE -complete . Problem osiągalności dla sieci Petriego przez długi czas był znany jako EXPSPACE -trudny , ale okazał się być nieelementarny, więc nie jest w EXPSPACE .

Stosunek do innych klas

EXPSPACE jest znany jako ścisły nadzbiór PSPACE , NP i P . Podejrzewa się, że jest to ścisły nadzbiór EXPTIME , jednak nie jest to znane.

Zobacz też

• Złożoność gry

Bibliografia

• Berman, Leonard (1 maja 1980). „Złożoność teorii logicznych” . Informatyka teoretyczna . 11 (1): 71–77. doi : 10.1016/0304-3975(80)90037-7 .
• Michaela Sipsera (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. Numer ISBN 0-534-94728-X.Sekcja 9.1.1: Wykładnicza kompletność przestrzeni, s. 313–317. Pokazuje, że określenie równoważności wyrażeń regularnych z potęgowaniem jest zakończone EXPSPACE.