Złożoność obliczeniowa/Test 11: Obliczenia równoległe

From Studia Informatyczne

Algorytm równoległy uważamy za efektywny, jeśli

jego złożoność czasowa oraz liczba procesorów są wielomianowe

jego złożoność czasowa jest polilogarytmiczna, a liczba procesorów dowolna

jego złożoność czasowa jest polilogarytmiczna, a liczba procesorów wielomianowa

można go zrealizować na maszynie PRAM w czasie logarytmicznym


Problem REACHABILITY rozwiązujemy na maszynie PRAM

w czasie O(\log n) i pracy O(n^3)

w czasie O(\log^2n) i pracy O(n^3/\log n)

w czasie O(\log^2n) i pracy O(n^3\log n)

żadna z pozostałych odpowiedzi nie jest poprawna


Jeśli rodzina obwodów logicznych jest jednostajna, to

głebokośc obwodu jest logarytmiczna względem liczby bramek wejściowych

liczba bramek jest wielomianowa względem liczby bramek wejściowych

opis bramki dla dowolnej liczby bramek wejściowych można wygenerować tym samym algorytmem

złożoność czasowa jest obliczalną funkcją liczby bramek wejściowych


W klasie NC znajdują się

wszystkie problemy o polilogarytmicznym czasie rozwiązania na wielomianowej liczbie procesorów

wszystkie problemy rozwiązywalne niedeterministycznie w logarytmicznej pamięci

niektóre problemy NP-zupełne

wszystkie problemy rozwiązywalne w czasie pseudowielomianowym


Język L jest P-zupełny, jeśli należy do P oraz

każdy język w P redukuje sie wielomianowo do L

redukuje się w sensie redukcji Turinga do każdego języka w P

każdy język w P redukuje się logarytmicznie do L

nie należy do klasy L


W redukcji opisanej w dowodzie P-zupełności problemu CIRCUIT VALUE,

wyjściowy obwód konstruowany jest algorytmem działającym w logarytmicznej pamięci roboczej

wyjściowy obwód ma logarytmiczną głębokość

wyjściowy obwód ma wielomianowy rozmiar

jej złożoność mierzy się względem długości opisu maszyny Turinga

jej złożoność mierzy się względem długości słowa wejściowego do maszyny Turinga


W randomizowanym obwodzie logicznym

liczba bitów losowych jest zawsze stała

akceptacja słowa należacego do rozpoznawanego języka zachodzi z prawdopodobieństwem co najmniej \log n

liczba bitów losowych zależy od rozmiaru danych wejściowych

każdy bit losowy może byc wykorzystany tylko w jednej bramce

prawdopodobieństwo zaakceptowania słowa spoza języka jest ograniczone od góry przez stałą