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

Problem QSAT jest:

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{EXPSPACE}} -zupełny Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PH}} -zupełny Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE}} -zupełny Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{EXP}} -zupełny Źle

żadne z powyższych Źle

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

dane wejściowe są nieskończonymi strukturami Źle

dane wejściowe są zapisane zwięźle Dobrze

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

w swej istocie operują na nieskończonych strukturach Dobrze

dane wyjściowe są nieskończonymi strukturami Źle

Prawdziwość formuły QSAT jest równoważna istnieniu w odpowiadającej grze Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE}}

strategii wygrywającej dla drugiego gracza Źle

nieskończonej rozgrywki Źle

strategii wygrywającej dla pierwszego gracza Dobrze

Rzeczywista gra GEOGRAPHY jest modelowana przy pomocy

grafu nieskończonego Źle

formuły logicznej Źle

grafu skończonego Dobrze

wyrażenia regularnego Źle

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

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE} \subseteq \cc{EXPSPACE} \subseteq \cc{EXP} \subseteq \cc{NEXP}} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE} \subseteq \cc{EXP} \subseteq \cc{NEXP} \subseteq \cc{EXPSPACE}} Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{EXPSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXP} \subseteq \cc{PSPACE}} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXP} \subseteq \cc{EXPSPACE}} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{EXP} \subseteq \cc{PSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXPSPACE}} Źle

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

w górę Dobrze

nie przenosi się Źle

w dół Źle

nie wiadomo Źle

Problemem Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{EXPSPACE}} -zupełnym jest sprawdzanie równoważności wyrażeń regularnych:

klasycznych (suma, konkatenacja i gwiazdka) Źle

rozszerzonych o potęgowanie Dobrze

rozszerzonych o potęgowanie i negację Źle

żadne z powyższych Źle