Złożoność obliczeniowa/Test 14: Pamięć wielomianowa i złożoność wykładnicza

From Studia Informatyczne

Problem QSAT jest:

\cc{EXPSPACE}-zupełny

\cc{PH}-zupełny

\cc{PSPACE}-zupełny

\cc{EXP}-zupełny

żadne z powyższych


Wersje periodyczne problemów są trudniejsze obliczeniowo, gdyż:

dane wejściowe są nieskończonymi strukturami

dane wejściowe są zapisane zwięźle

dane wyjściowe muszą być prezentowane zwięźle

w swej istocie operują na nieskończonych strukturach

dane wyjściowe są nieskończonymi strukturami


Prawdziwość formuły QSAT jest równoważna istnieniu w odpowiadającej grze \cc{PSPACE}

strategii wygrywającej dla drugiego gracza

nieskończonej rozgrywki

strategii wygrywającej dla pierwszego gracza


Rzeczywista gra GEOGRAPHY jest modelowana przy pomocy

grafu nieskończonego

formuły logicznej

grafu skończonego

wyrażenia regularnego


Relacje dotyczące klas wykładniczych przedstawiają się następująco:

\cc{PSPACE} \subseteq \cc{EXPSPACE} \subseteq \cc{EXP} \subseteq \cc{NEXP}

\cc{PSPACE} \subseteq \cc{EXP} \subseteq \cc{NEXP} \subseteq \cc{EXPSPACE}

\cc{EXPSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXP} \subseteq \cc{PSPACE}

\cc{PSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXP} \subseteq \cc{EXPSPACE}

\cc{EXP} \subseteq \cc{PSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXPSPACE}


Równość klas deterministycznych i niedeterministycznych czasowych przenosi się pomiędzy poziomami:

w górę

nie przenosi się

w dół

nie wiadomo


Problemem \cc{EXPSPACE}-zupełnym jest sprawdzanie równoważności wyrażeń regularnych:

klasycznych (suma, konkatenacja i gwiazdka)

rozszerzonych o potęgowanie

rozszerzonych o potęgowanie i negację

żadne z powyższych