Jaka jest duża wersja NC?

rejestruje ideę skutecznie parallelizable i jeden interpretacja jest to, że problem można rozwiązać w czasie za pomocą równoległych procesorów dla niektórych stałych , . Moje pytanie brzmi, czy istnieje analogiczna klasa złożoności, w której czas wynosi a liczba procesorów wynosi . Jako pytanie wypełniające puste: $\mathsf{NC}$ $O(\log^c n)$ $O(n^k)$ $c$ $k$ $n^c$ $2^{n^k}$

oznacza jak__ oznacza $\mathsf{NC}$ $\mathsf{P}$ $\mathsf{EXP}$

W szczególności interesuje mnie model, w którym mamy wykładniczą liczbę komputerów rozmieszczonych w sieci z wielomianowo ograniczonym stopniem (powiedzmy, że sieć jest niezależna od danych wejściowych / problemów lub przynajmniej w jakiś sposób łatwa do zbudowania, lub jakiekolwiek inne rozsądne założenie o jednolitości ). Na każdym etapie:

Każdy komputer odczytuje wielomianową liczbę wielomianowych wiadomości otrzymanych w poprzednim kroku czasowym.
Każdy komputer wykonuje pewne obliczenia czasu policyjnego, które mogą zależeć od tych komunikatów.
Każdy komputer przekazuje wiadomość (o długości polilinii) każdemu swojemu sąsiadowi.

Jak nazywa się klasa złożoności odpowiadająca tego rodzaju modelom? Jakie jest dobre miejsce do czytania o takich klasach złożoności? Czy są jakieś kompletne problemy dla takiej klasy?

cc.complexity-theory reference-request complexity-classes circuit-complexity dc.parallel-comp Artem Kaznatcheev
źródło

powiązane pytanie, myślę, że: cstheory.stackexchange.com/q/2788/1037

Artem Kaznatcheev

Mamy

N C^{k} = A S p a c e T i m e (O (\log n), (\log n)^{k})

$NC^k = ASpaceTime(O(\log n), (\log n)^k)$

N C = A S p a c e T i m e (O (\log n), (\log n)^{O (1)})

$NC = ASpaceTime(O(\log n), (\log n)^{O(1)})$

. Tak więc klasa odpowiadająca

może być czymś w rodzaju

P = T i m e (n^{O (1)})

$P = Time(n^{O(1)})$

E X P = T i m e (2^{n^{O (1)}})

$EXP = Time(2^{n^{O(1)}})$

N C^{k}

$NC^k$

. To tylko niektóre manipulacje algebraiczne, nie sprawdziłem, czy spełnia twoje wymagania, ale myślę, że spełni trzy warunki, ale nie będzie miał wykładniczo wielu komputerów. Myślę, że powinieneś zrezygnować z tego wymogu inaczej (więcej)a następnie odpowiednią klasą dla

będzie

A S p a c e T i m e (n^{O (1)}, 2^{O (\log n)^{k}})

$ASpaceTime(n^{O(1)}, 2^{O(\log n)^k})$

N C

$NC$

A S p a c e T i m e (n^{O (1)}, 2^{(\log n)^{O (1)}})

$ASpaceTime(n^{O(1)}, 2^{(\log n)^{O(1)}})$

Kaveh

otrzymany klasa zawiera

i analogii nie będzie posiadał jak

E X P

$EXP$

N C \subseteq P

$NC \subseteq P$

Kaveh

Nie rozumiem, skąd masz

jak złożoność przestrzeni. O ile wiem,

pozwala wielomianowo wiele bramek. Jeśli chcemy pójść zgodnie z wytycznymi twojego analogu, powinniśmy spojrzeć na

jako

l o g n

$log n$

N C

$NC$

N C

$NC$

a wtedy szukana klasa złożoności jest czymś jak

P T / W K (l o g^{c} n, n^{k}) / p o l y

$PT/WK(log^c n,n^k)/poly$

. Miałem jednak nadzieję, że istnieje lepsza charakterystyka niż to.

P T / W K (n^{c}, 2^{n^{k}}) / p o l y

$PT/WK(n^c ,2^{n^k})/poly$

Artem Kaznatcheev

Jest to standard (chociaż nie ma go w Zoo Złożoności), sprawdź np. Ruzzo, „O jednolitej złożoności obwodu”, 1981. Myślę też, że powinieneś pracować z klasami jednorodnymi, każda funkcja ma wykładniczą zmienność wielkości wykładniczej / obwody głębokości logicznej 2 (i spełni to trzy warunki, jeśli użyjemy ograniczonego wachlowania i

głębokości

). I jak powiedziałem, jeśli istnieje wykładniczo wiele węzłów, wówczas analogia nie ma zastosowania. Również Główną właściwością równoległych obliczeniach jest oszczędność czasu, np to jest poli-log razem w przypadku

. Myślę, że czas quasi-wielomianowy odpowiadałby czasowi poliblog.

\log n

$\log n$

N C

$NC$

Kaveh

Odpowiedzi:

Wierzę, że klasa szukasz jest . Załóżmy, że masz procesorów spełniających wymagania: $PSPACE$ $exp(n^k) = 2^{O(n^k)}$

Każdy komputer odczytuje wielomianową liczbę wielomianowych wiadomości otrzymanych w poprzednim kroku czasowym.

Każdy komputer wykonuje pewne obliczenia czasu policyjnego, które mogą zależeć od tych komunikatów.

Każdy komputer przekazuje wiadomość (o długości polilinii) każdemu swojemu sąsiadowi.

Może to być wzór poprzez obwód o warstwy, przy czym każda warstwa ma „bramki”, a każdy z „brama” wykonuje się obliczenie wielomianowe czasu (spełniający część 2) z wielomianem wachlarz (spełniający część 1) i ma wielomianowy wachlarz (spełniający część 3). $poly(n)$ $exp(n^k)$

Ponieważ każda bramka oblicza funkcję czasu wielomianowego, każda z nich może być zastąpiona przez obwód wielkości wielomianowej (z AND / OR / NOT) w zwykły sposób. Zauważ, że wielomianowe wachlarze i wachlarze mogą być ustawione na 2, zwiększając tylko głębokość o współczynnik . Co zostało to obwodu głębokość jednolite $O(\log n)$ $poly(n)$ I / I / nie bram. Jest to dokładnie naprzemienne wielomianu czas, który jest dokładnie . $exp(n^k)$ $PSPACE$

Ryan Williams
źródło

Ryan, nie rozumiem, jak rozkładasz wykładniczą liczbę komputerów na wielomianowo wiele warstw. Wydaje mi się, że głębokość może być wykładnicza. Czy mógłbyś wyjaśnić to nieco bardziej, dlaczego jest to możliwe? Wydaje mi się również, że trywialna konstrukcja obwodu CNF o dowolnie wybranej funkcji jako obwód wachlarza 2 spełniałaby wymagania, czy coś mi brakuje?

Kaveh

@Kaveh: Nie rozumiem twojego pierwszego pytania. Około drugiego, chociaż dla każdej funkcji istnieje obwód o głębokości wykładniczej wielkości 2, NC (poli) wymaga, aby można było generować obwody równomiernie, więc nie można wytwarzać dowolnych obwodów dla każdego rozmiaru wejściowego.

Robin Kothari

@Robin, dzięki. Prawdopodobnie mylę rzeczy. (Wydaje mi się, że głębokość obwodów odpowiadających PSpace powinna być wykładnicza, również myślę, że PSpace jest EXP, ponieważ L jest do P, więc stwierdzenie tego samego, gdy L jest zastąpione NC, jest dla mnie dziwne, czuję, że jesteśmy klasą opieka powinna mieścić się między PSpace a EXP.) Muszę pomyśleć trochę więcej, aby zrozumieć, co się tutaj dzieje.

Kaveh

@Kaveh, przypisałem liczbę warstw (tj. Głębokość), które mają być wykładnicze, więc głębokość nie może być wykładnicza z definicji. Istnieje wykładniczo wiele procesorów, więc Twój CNF będzie wymagał wykładniczego wachlowania, co narusza jeden z warunków. Głębokość obwodów wielkości wykładniczej odpowiadających PSPACE jest wielomianowa. Powodem tego jest to, że obie analogie są w pewnym sensie „poprawne” („PSPACE ma EXP tak jak L jest P”, a „PSPACE ma EXP tak jak NC jest P”) jest dlatego, że PSPACE = przemienny wielomian Czas. Nie wiemy, czy L = przemienny czas logarytmiczny (jest to NC1).

Ryan Williams

Myślę, że lepiej rozumiem sytuację po przeczytaniu twoich i Robina komentarzy, dzięki.

Kaveh

Jak mówi Ryan, ta klasa to PSPACE. Ta klasa jest często nazywana w literaturze NC (poli). Oto bezpośredni cytat z pracy QIP = PSPACE :

Rozważamy skalowany wariant NC, który jest klasą złożoności NC (poli), która składa się ze wszystkich funkcji obliczalnych przez rodziny jednorodnych wielomianowych obwodów boolowskich o wielomianowej głębokości. (Notacja NC (2 ^poli ) była wcześniej używana również dla tej klasy [11].) W przypadku problemów decyzyjnych wiadomo, że NC (poli) = PSPACE [10].

[10] A. Borodin. O powiązaniu czasu i przestrzeni z rozmiarem i głębokością. SIAM Journal on Computing, 6: 733– 744, 1977.

[11] A. Borodin, S. Cook i N. Pippenger. Równoległe obliczenia dla dobrze wyposażonych pierścieni i ograniczonych przestrzennie maszyn probabilistycznych. Information and Control, 58: 113–136, 1983.

Jednym ze sposobów na to jest bezpośrednie udowodnienie obu wtrąceń. Aby zobaczyć, że NC (poli) znajduje się w PSPACE, zauważ, że możemy rekurencyjnie obliczać wynik końcowej bramki i będziemy potrzebować tylko stosu wielkości równego głębokości obwodu, który jest wielomianem. Aby pokazać, że PSPACE jest w NC (poli), należy zauważyć, że QBF, który jest kompletny z PSPACE, można zapisać jako wielomianowy obwód głębokości z wykładniczo wieloma bramkami w zwykły sposób - istniejący kwantyfikator jest bramką OR, kwantyfikatorem forall jest bramą AND. Ponieważ istnieje tylko wielomianowo wiele kwantyfikatorów, jest to wielomianowy obwód głębokości.

Robin Kothari
źródło