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

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

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

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

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

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

Problem REACHABILITY rozwiązujemy na maszynie PRAM

w czasie $O(\log n)$ i pracy $O(n^{3})$ Źle

w czasie $O(\log ^{2}n)$ i pracy $O(n^{3}/\log n)$ Źle

w czasie $O(\log ^{2}n)$ i pracy $O(n^{3}\log n)$ Dobrze

żadna z pozostałych odpowiedzi nie jest poprawna Źle

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

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

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

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

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

W klasie NC znajdują się

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

wszystkie problemy rozwiązywalne niedeterministycznie w logarytmicznej pamięci Dobrze

niektóre problemy NP-zupełne Źle

wszystkie problemy rozwiązywalne w czasie pseudowielomianowym Źle

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$ Źle

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

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

nie należy do klasy L Źle

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 Dobrze

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

wyjściowy obwód ma wielomianowy rozmiar Dobrze

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

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

W randomizowanym obwodzie logicznym

liczba bitów losowych jest zawsze stała Źle

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

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

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

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