Złożoność obliczeniowa/Test 13: Pamięć logarytmiczna i hierarchia wielomianowa

From Studia Informatyczne

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 \cc{coNL}

UNDIRECTED REACHABILITY należy do klasy \cc{L}

REACHABILITY należy do klasy \cc{L}

UNDIRECTED REACHABILITY należy do klasy \cc{NL}

REACHABILITY należy do klasy \cc{NL}


Klasa \cc{DP}

zawiera w sobie \cc{NP} i \cc{coNP}

zawiera w sobie \cc{PH}

zawiera się w \cc{PH}

zawiera się w \cc{NP} i \cc{coNP}


Maszyny alternujące są specjalnym przypadkiem maszyn niedeterministycznych. {FALSE}


\cc{AP} 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 \sum_{i} \cc{P} jest definiowana poprzez wyrocznię na niższy poziom oraz:

maszyny z klasy \cc{NP}

maszyny z klasy \cc{P}

maszyny z klasy \cc{coNP}


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ść