Stornierung und Determinante

9

Der Berkowitz-Algorithmus liefert eine Polynomgrößenschaltung mit logarithmischer Tiefe zur Determinante einer quadratischen Matrix unter Verwendung von Matrixleistungen. Der Algorithmus verwendet implizit die Löschung. Ist eine Aufhebung wesentlich, um eine Schaltung mit Polynomgröße mit logarithmischer oder linearer Tiefe zu erhalten, um die Determinante (und eine mögliche beste Schaltung für Permanent) zu berechnen? Gibt es für diese Probleme vollständig exponentielle (nicht nur superpolynomielle oder subexponentielle) Untergrenzen für diese Probleme unter Verwendung von Schaltungen ohne Aufhebung?

circuit-complexity algebraic-complexity permanent arithmetic-circuits determinant T ....
quelle

2

In einem intuitiven Sinne ist die Determinante ohne Stornierungen dieselbe wie die permanente

Sasho Nikolov

11

Ja, Stornierungen sind erforderlich und es gibt Untergrenzen für monotone und nicht kommutative Modelle, bei denen Stornierungen nicht möglich sind. Siehe Diskussion in monotonen Rechenschaltungen . Eine Übersicht über die Komplexität aritmetischer Schaltkreise finden Sie unter http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

Noam
quelle

1

f = g_{1} + g_{2}

$f = g_1 + g_2$

f

$f$

g_{1}

$g_1$

g_{2}

$g_2$

f = g_{1} \times g_{2}

$f = g_1 \times g_2$

g_{1}

$g_1$

g_{2}

$g_2$ . Die Untergrenze von Jerrum-Snir funktioniert, solange die Schaltung die Eigenschaft erfüllt, dass die formalen Monome der Wurzel gleich den Nicht-Null-Monomen des berechneten Polynoms sind.

Ramprasad

1

Ich denke, dieses Papier beantwortet Ihre Frage direkt.

Die Stornierung ist für die Berechnung der Determinante exponentiell leistungsfähig

$n \times n$ $n(2^{n-1}-1)$

Thatchaphol
quelle

Stornierung und Determinante

Antworten: