Złożoność obliczeniowa/Test 13: Pamięć logarytmiczna i hierarchia wielomianowa: Różnice pomiędzy wersjami
Nie podano opisu zmian |
m Zastępowanie tekstu - "\cc{" na "\mathrm{" |
||
| Linia 10: | Linia 10: | ||
<quiz> | <quiz> | ||
W dowodzie twierdzenia Immermana-Szelepcsényi'ego korzystamy z faktu, iż: | W dowodzie twierdzenia Immermana-Szelepcsényi'ego korzystamy z faktu, iż: | ||
<rightoption>REACHABILITY należy do klasy <math>\ | <rightoption>REACHABILITY należy do klasy <math>\mathrm{coNL}</math></rightoption> | ||
<wrongoption>UNDIRECTED REACHABILITY należy do klasy <math>\ | <wrongoption>UNDIRECTED REACHABILITY należy do klasy <math>\mathrm{L}</math></wrongoption> | ||
<wrongoption>REACHABILITY należy do klasy <math>\ | <wrongoption>REACHABILITY należy do klasy <math>\mathrm{L}</math></wrongoption> | ||
<wrongoption>UNDIRECTED REACHABILITY należy do klasy <math>\ | <wrongoption>UNDIRECTED REACHABILITY należy do klasy <math>\mathrm{NL}</math></wrongoption> | ||
<wrongoption>REACHABILITY należy do klasy <math>\ | <wrongoption>REACHABILITY należy do klasy <math>\mathrm{NL}</math></wrongoption> | ||
</quiz> | </quiz> | ||
<quiz> | <quiz> | ||
Klasa <math>\ | Klasa <math>\mathrm{DP}</math> | ||
<rightoption>zawiera w sobie <math>\ | <rightoption>zawiera w sobie <math>\mathrm{NP}</math> i <math>\mathrm{coNP}</math></rightoption> | ||
<wrongoption>zawiera w sobie <math>\ | <wrongoption>zawiera w sobie <math>\mathrm{PH}</math></wrongoption> | ||
<rightoption>zawiera się w <math>\ | <rightoption>zawiera się w <math>\mathrm{PH}</math></rightoption> | ||
<wrongoption>zawiera się w <math>\ | <wrongoption>zawiera się w <math>\mathrm{NP}</math> i <math>\mathrm{coNP}</math></wrongoption> | ||
</quiz> | </quiz> | ||
| Linia 31: | Linia 31: | ||
<quiz> | <quiz> | ||
<math>\ | <math>\mathrm{AP}</math> jest klasą języków, które mogą być akceptowane: | ||
<wrongoption>w niedeterministycznym czasie wielomianowym</wrongoption> | <wrongoption>w niedeterministycznym czasie wielomianowym</wrongoption> | ||
<wrongoption>w alternującej pamięci wielomianowej</wrongoption> | <wrongoption>w alternującej pamięci wielomianowej</wrongoption> | ||
| Linia 41: | Linia 41: | ||
<quiz> | <quiz> | ||
Klasa <math>\sum_{i} \ | Klasa <math>\sum_{i} \mathrm{P}</math> jest definiowana poprzez wyrocznię na niższy poziom oraz: | ||
<rightoption>maszyny z klasy <math>\ | <rightoption>maszyny z klasy <math>\mathrm{NP}</math></rightoption> | ||
<wrongoption>maszyny z klasy <math>\ | <wrongoption>maszyny z klasy <math>\mathrm{P}</math></wrongoption> | ||
<wrongoption>maszyny z klasy <math>\ | <wrongoption>maszyny z klasy <math>\mathrm{coNP}</math></wrongoption> | ||
</quiz> | </quiz> | ||
Aktualna wersja na dzień 23:29, 11 cze 2020
Twierdzenie Immermana-Szelepcsényi'ego mówi o tym, że klasy złożoności:
deterministycznej pamięciowej są zamknięte na dopełnienie
niedeterministycznej pamięciowej są zamknięte na dopełnienie
deterministycznej czasowej są zamknięte na dopełnienie
niedeterministycznej czasowej są zamknięte na dopełnienie
W dowodzie twierdzenia Immermana-Szelepcsényi'ego korzystamy z faktu, iż:
REACHABILITY należy do klasy
UNDIRECTED REACHABILITY należy do klasy
REACHABILITY należy do klasy
UNDIRECTED REACHABILITY należy do klasy
REACHABILITY należy do klasy
Klasa
zawiera w sobie i
zawiera w sobie
zawiera się w
zawiera się w i
Maszyny alternujące są specjalnym przypadkiem maszyn niedeterministycznych. {FALSE}
jest klasą języków, które mogą być akceptowane:
w niedeterministycznym czasie wielomianowym
w alternującej pamięci wielomianowej
w niedeterministycznej pamięci wielomianowej
w deterministycznej pamięci wielomianowej
w alternującym czasie wielomianowym
Klasa jest definiowana poprzez wyrocznię na niższy poziom oraz:
maszyny z klasy
maszyny z klasy
maszyny z klasy
Czy hierarchia wielomianowa ma problemy zupełne?
na każdym poziomie, lecz nie jako całość
jako całość, natomiast na poziomach nie
nie posiada zarówno jako całość jak i na poziomach
na każdym poziomie i jako całość
