Cancelación y determinante

9

El algoritmo de Berkowitz proporciona un circuito de tamaño polinómico con profundidad logarítmica para determinar una matriz cuadrada utilizando potencias matriciales. El algoritmo utiliza implícitamente la cancelación. ¿Es esencial la cancelación para lograr un circuito de tamaño polinómico con profundidad logarítmica o lineal para calcular el determinante (y cualquier mejor circuito posible para permanente)? ¿Existen límites inferiores totalmente exponenciales (no solo superpolinomiales o subexponenciales) para estos problemas utilizando circuitos sin cancelación?

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

2

en cierto sentido intuitivo, sin cancelaciones, el determinante es lo mismo que lo permanente

Sasho Nikolov

11

Sí, se necesitan cancelaciones y existen límites inferiores para los modelos monótonos y no conmutativos donde las cancelaciones son imposibles. Vea la discusión en Circuitos aritméticos monótonos . Se puede encontrar una encuesta sobre la complejidad del circuito aritmético en http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

Noam
fuente

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$ . El límite inferior de Jerrum-Snir funciona siempre que el circuito satisfaga la propiedad de que los monomios formales de la raíz son iguales a los monomios distintos de cero del polinomio calculado.

Ramprasad

1

Creo que este documento responde directamente a su pregunta.

La cancelación es exponencialmente poderosa para calcular el determinante

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

Thatchaphol
fuente

Cancelación y determinante

Respuestas: