Złożoność obliczeniowa/Test 14: Pamięć wielomianowa i złożoność wykładnicza: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
m Zastępowanie tekstu - "\cc{" na "\mathrm{"
 
Linia 1: Linia 1:
<quiz>
<quiz>
Problem QSAT jest:  
Problem QSAT jest:  
<wrongoption><math>\cc{EXPSPACE}</math>-zupełny</wrongoption>
<wrongoption><math>\mathrm{EXPSPACE}</math>-zupełny</wrongoption>
<wrongoption><math>\cc{PH}</math>-zupełny</wrongoption>
<wrongoption><math>\mathrm{PH}</math>-zupełny</wrongoption>
<rightoption><math>\cc{PSPACE}</math>-zupełny</rightoption>
<rightoption><math>\mathrm{PSPACE}</math>-zupełny</rightoption>
<wrongoption><math>\cc{EXP}</math>-zupełny</wrongoption>
<wrongoption><math>\mathrm{EXP}</math>-zupełny</wrongoption>
<wrongoption>żadne z powyższych</wrongoption>
<wrongoption>żadne z powyższych</wrongoption>
</quiz>
</quiz>
Linia 20: Linia 20:


<quiz>
<quiz>
Prawdziwość formuły QSAT jest równoważna istnieniu w odpowiadającej grze <math>\cc{PSPACE}</math>  
Prawdziwość formuły QSAT jest równoważna istnieniu w odpowiadającej grze <math>\mathrm{PSPACE}</math>  
<wrongoption>strategii wygrywającej dla drugiego gracza</wrongoption>
<wrongoption>strategii wygrywającej dla drugiego gracza</wrongoption>
<wrongoption>nieskończonej rozgrywki</wrongoption>
<wrongoption>nieskończonej rozgrywki</wrongoption>
Linia 38: Linia 38:
<quiz>
<quiz>
Relacje dotyczące klas wykładniczych przedstawiają się następująco:  
Relacje dotyczące klas wykładniczych przedstawiają się następująco:  
<wrongoption><math>\cc{PSPACE} \subseteq \cc{EXPSPACE} \subseteq \cc{EXP} \subseteq \cc{NEXP}</math></wrongoption>
<wrongoption><math>\mathrm{PSPACE} \subseteq \mathrm{EXPSPACE} \subseteq \mathrm{EXP} \subseteq \mathrm{NEXP}</math></wrongoption>
<rightoption><math>\cc{PSPACE} \subseteq \cc{EXP} \subseteq \cc{NEXP} \subseteq \cc{EXPSPACE}</math></rightoption>
<rightoption><math>\mathrm{PSPACE} \subseteq \mathrm{EXP} \subseteq \mathrm{NEXP} \subseteq \mathrm{EXPSPACE}</math></rightoption>
<wrongoption><math>\cc{EXPSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXP} \subseteq \cc{PSPACE}</math></wrongoption>
<wrongoption><math>\mathrm{EXPSPACE} \subseteq \mathrm{NEXP} \subseteq \mathrm{EXP} \subseteq \mathrm{PSPACE}</math></wrongoption>
<wrongoption><math>\cc{PSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXP} \subseteq \cc{EXPSPACE}</math></wrongoption>
<wrongoption><math>\mathrm{PSPACE} \subseteq \mathrm{NEXP} \subseteq \mathrm{EXP} \subseteq \mathrm{EXPSPACE}</math></wrongoption>
<wrongoption><math>\cc{EXP} \subseteq \cc{PSPACE} \subseteq \cc{NEXP} \subseteq \cc{EXPSPACE}</math></wrongoption>
<wrongoption><math>\mathrm{EXP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{NEXP} \subseteq \mathrm{EXPSPACE}</math></wrongoption>
</quiz>
</quiz>


Linia 56: Linia 56:


<quiz>
<quiz>
Problemem <math>\cc{EXPSPACE}</math>-zupełnym jest sprawdzanie równoważności wyrażeń regularnych:  
Problemem <math>\mathrm{EXPSPACE}</math>-zupełnym jest sprawdzanie równoważności wyrażeń regularnych:  
<wrongoption>klasycznych (suma, konkatenacja i gwiazdka)</wrongoption>
<wrongoption>klasycznych (suma, konkatenacja i gwiazdka)</wrongoption>
<rightoption>rozszerzonych o potęgowanie</rightoption>
<rightoption>rozszerzonych o potęgowanie</rightoption>

Aktualna wersja na dzień 23:29, 11 cze 2020

Problem QSAT jest:

EXPSPACE-zupełny

PH-zupełny

PSPACE-zupełny

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 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:

PSPACE⊆EXPSPACE⊆EXP⊆NEXP

PSPACE⊆EXP⊆NEXP⊆EXPSPACE

EXPSPACE⊆NEXP⊆EXP⊆PSPACE

PSPACE⊆NEXP⊆EXP⊆EXPSPACE

EXP⊆PSPACE⊆NEXP⊆EXPSPACE


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

w górę

nie przenosi się

w dół

nie wiadomo


Problemem 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

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Test_14:_Pamięć_wielomianowa_i_złożoność_wykładnicza&oldid=77672”