Determinanty i mnożenie macierzy - podobieństwo i różnice w złożoności algorytmicznej i wielkości obwodu arytmetycznego

Próbuję zrozumieć związek między złożonością algorytmiczną a złożonością obwodów determinant i mnożenia macierzy.

Wiadomo, że wyznacznik macierzy można obliczyć w czasie , gdzie to minimalny czas wymagany do pomnożenia dowolnych dwóch macierzy. Wiadomo również, że najlepszą złożonością obwodów wyznaczników jest wielomian na głębokości i wykładniczy na głębokości 3. Ale złożoność obwodu mnożenia macierzy dla dowolnej stałej głębokości jest tylko wielomianem. $n\times n$ $\tilde{O}(M(n))$ $M(n)$ $n\times n$ $O(\log^{2}(n))$

Dlaczego istnieje różnica w złożoności obwodu dla wyznaczników i mnożenia macierzy, skoro wiadomo, że z perspektywy algorytmu obliczanie wyznaczników jest podobne do mnożenia macierzy? W szczególności, dlaczego złożoność obwodów ma lukę wykładniczą na głębokości- ? $3$

Prawdopodobnie wyjaśnienie jest proste, ale nie rozumiem. Czy istnieje wyjaśnienie „rygor”?

Zobacz także: Najmniejsza znana formuła wyznacznika

algebraic-complexity arithmetic-circuits matrix-product determinant T ....
źródło

Odpowiedzi:

Rozważ problem z wartością obwodu i ocenę formuły boolowskiej dla różnych małych klas złożoności. Ich deterministyczna złożoność sekwencyjna w czasie jest podobna, o ile wiemy, ale bardzo różnią się od perspektywy złożoności obwodu. Podobieństwo w jednym konkretnym typie zasobu w jednym modelu nie oznacza podobieństwa do innych zasobów w innych modelach. Jeden problem może być taki, że możemy wykorzystać obliczenia równoległe dla jednego, podczas gdy nie możemy tego zrobić dla innego, ale ich złożoność czasowa może być taka sama.

Kiedy możemy spodziewać się silniejszego związku między złożonością dwóch problemów między modelami i różnymi zasobami? Gdy są solidne redukcje między nimi w obu kierunkach, które szanują zasoby w tych modelach.

Edycja: mnożenie ma obwody o głębokości podwykładniczej wielkości 3. Podanie tego rodzaju dolnej granicy dla wyznacznika pokazałoby, że nie jest w oddzielenie go od który nie jest znany. $\mathsf{NL}$ $\mathsf{NC^2}$

Kaveh
źródło

„zwielokrotnienie ma obwody o głębokości podwykładniczej wielkości 3.” Sądzę, że mnożenie ma wielkość obwodu na dowolnej głębokości, ponieważ polega tylko na wyciągnięciu zmiennych i pomnożeniu ich w określonej kolejności oraz dodaniu produktów pośrednich.

O (n^{3})

$O(n^{3})$

n^{2}

$n^{2}$

T ....

Mnożenie dwóch liczb całkowitych jest zakończone dla i dlatego nie jest w .

T C^{0}

$\mathsf{TC^0}$

A C^{0}

$\mathsf{AC^0}$

Kaveh

Na razie patrzę tylko na sekwencyjną złożoność.

T ....

Nie jestem pewien, czy śledzę twój komentarz. Myślę, że mój post odpowiada na pytanie w ustawieniu boolowskim (w pytaniu nie było pierwotnie obwodów arytmetycznych IIRC). Jeśli chodzi o ustawienie obwodu arytmetycznego, niewiele wiem, mam nadzieję, że inni odpowiedzą na pytanie.

Kaveh

Powiedziałbym, że luka w ustawieniach arytmetycznych mówi nam, że mnożenie macierzy jest z natury znacznie bardziej równoległym zadaniem niż wyznacznik. Innymi słowy, podczas gdy sekwencyjne złożoności obu problemów są ze sobą ściśle powiązane, ich równoległe złożoności nie są tak blisko siebie.

$D(n)$ $n\times n$

O (\log n) \leq D (n) \leq O (\log^{2} n) .

$O(\log n)\le D(n) \le O(\log^2 n).$

3

$3$ obwód arytmetyczny obliczający mnożenie macierzy, podane wzorem

(A \cdot B)_{i j} = \sum_{k} A_{i k} B_{k j}

$(A\cdot B)_{ij}=\sum_k A_{ik}B_{kj}$

Bruno
źródło

Nie wiem, czy jest to odpowiedź na pytanie „dlaczego złożoność obwodów ma lukę wykładniczą na głębokości 3?”, Ale przynajmniej macie dowód na to, że jest to praca Csanky'ego.

Bruno,

Jeśli dobrze rozumiem, sugerujesz: aby mieć wielomianową liczbę procesorów, potrzebna jest głębia logarytmiczna?

T ....

Nie pamiętam dokładnie takiego modelu, jakiego użył Csanky. Właściwie rozważa to, co dziś nazywamy obwodami arytmetycznymi z ograniczonym wachlowaniem . Zatem dolna granica jest dość trywialna, a moje porównanie z mnożeniem macierzy nie ma znaczenia.

Bruno,