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

Problem QSAT jest:

$\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$-zupełny Źle

$\mathrm{P}\mathrm{H}$-zupełny Źle

$\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$-zupełny Dobrze

$\mathrm{E}\mathrm{X}\mathrm{P}$-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 $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$

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:

$\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}$ Źle

$\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ Dobrze

$\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ Źle

$\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ Źle

$\mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}\subseteq \mathrm{N}\mathrm{E}\mathrm{X}\mathrm{P}\subseteq \mathrm{E}\mathrm{X}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ Ź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 $\mathrm{E}\mathrm{X}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$-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