Determinanten und Matrixmultiplikation - Ähnlichkeit und Unterschiede in der algorithmischen Komplexität und der Größe der arithmetischen Schaltung

Ich versuche die Beziehung zwischen algorithmischer Komplexität und Schaltungskomplexität von Determinanten und Matrixmultiplikation zu verstehen.

Es ist bekannt, dass die Determinante einer Matrix in -Zeit berechnet werden kann , wobei die minimale Zeit ist, die erforderlich ist, um zwei beliebige Matrizen zu multiplizieren . Es ist auch bekannt, dass die beste Schaltungskomplexität von Determinanten in der Tiefe und exponentiell polynomisch ist $n\times n$ $\tilde{O}(M(n))$ $M(n)$ $n\times n$ $O(\log^{2}(n))$ in der Tiefe 3. Die Schaltungskomplexität der Matrixmultiplikation ist jedoch für jede konstante Tiefe nur ein Polynom.

Warum gibt es einen Unterschied in der Schaltungskomplexität für Determinanten und Matrixmultiplikation, obwohl bekannt ist, dass die Determinantenberechnung aus Algorithmusperspektive der Matrixmultiplikation ähnlich ist? Warum haben die Schaltungskomplexitäten in der Tiefe eine exponentielle Lücke ? $3$

Wahrscheinlich ist die Erklärung einfach, aber ich sehe es nicht. Gibt es eine Erklärung mit "Strenge"?

Schauen Sie auch in: Kleinste bekannte Formel für die Determinante

algebraic-complexity arithmetic-circuits matrix-product determinant T ....
quelle

Antworten:

Betrachten Sie das Schaltungswertproblem und die Auswertung der Booleschen Formel für verschiedene kleine Komplexitätsklassen. Die deterministische sequentielle Zeitkomplexität von ihnen ist nach unserem Kenntnisstand ähnlich, unterscheidet sich jedoch stark von der Perspektive der Schaltungskomplexität. Ähnlichkeit in einem bestimmten Ressourcentyp in einem Modell bedeutet keine Ähnlichkeit für andere Ressourcen in anderen Modellen. Ein Problem kann sein, dass wir die parallele Berechnung für eine ausnutzen können, während wir dies für eine andere nicht tun können, aber ihre sequentielle zeitliche Komplexität kann dieselbe sein.

Wann können wir eine robustere Beziehung zwischen der Komplexität zweier Probleme zwischen Modellen und unterschiedlichen Ressourcen erwarten? Wenn es sich um eine robuste Reduzierung zwischen ihnen in beide Richtungen handelt, werden die Ressourcen in diesen Modellen berücksichtigt.

Bearbeiten: Die Multiplikation hat Schaltungen mit subexponentieller Größentiefe 3. Der Nachweis einer solchen Untergrenze für die Determinante würde zeigen, dass sie nicht in und sie von trennt, was nicht bekannt ist. $\mathsf{NL}$ $\mathsf{NC^2}$

Kaveh
quelle

O (n^{3})

$O(n^{3})$

n^{2}

$n^{2}$

T C^{0}

$\mathsf{TC^0}$

A C^{0}

$\mathsf{AC^0}$

Ich betrachte vorerst nur die sequentielle Komplexität.

T ....

Ich bin mir nicht sicher, ob ich Ihrem Kommentar folge. Ich denke, mein Beitrag beantwortet die Frage in der Booleschen Einstellung (die Frage erwähnte ursprünglich keine arithmetischen Schaltungen IIRC). Für die Einstellung der Rechenschaltung weiß ich nicht viel, hoffentlich beantworten andere die Frage.

Kaveh

Ich würde sagen, dass die Lücke in den arithmetischen Einstellungen uns sagt, dass die Matrixmultiplikation von Natur aus eine viel parallelere Aufgabe ist als die Determinante. Mit anderen Worten, während die sequentiellen Komplexitäten beider Probleme eng miteinander verbunden sind, sind ihre parallelen Komplexitäten nicht so nahe beieinander.

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

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

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

Bruno
quelle

Ich weiß nicht, ob dies eine Antwort auf "Warum haben die Schaltungskomplexitäten in Tiefe 3 eine exponentielle Lücke?" Ist, aber zumindest haben Sie einen Beweis dafür, dass es sich um Csankys Artikel handelt.

Bruno

Wenn ich das richtig verstehe, implizieren Sie: Um eine Polynomzahl von Prozessoren zu haben, braucht man logarithmische Tiefe?

T ....

Ich erinnerte mich nicht an das genaue Modell, das Csanky verwendete. Eigentlich überlegt er, was wir heutzutage als arithmetische Schaltungen mit begrenztem Fan-In bezeichnen . Daher ist die Untergrenze ziemlich trivial und mein Vergleich mit der Matrixmultiplikation ist nicht relevant.

Bruno