Cancelamento e determinante

9

O algoritmo de Berkowitz fornece um circuito de tamanho polinomial com profundidade logarítmica para determinar uma matriz quadrada usando potências matriciais. O algoritmo usa implicitamente o cancelamento. O cancelamento é essencial para a obtenção de um circuito de tamanho polinomial com profundidade logarítmica ou linear para calcular o determinante (e qualquer melhor circuito possível para permanente)? Existem limites inferiores totalmente exponenciais (não apenas superpolinomiais ou subexponenciais) para esses problemas usando circuitos sem cancelamento?

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

2

em algum sentido intuitivo, sem cancelamentos o determinante é a mesma coisa que a permanente

Sasho Nikolov

11

Sim, são necessários cancelamentos e há limites mais baixos para modelos monótonos e não comutativos em que os cancelamentos são impossíveis. Veja a discussão em circuitos aritméticos monotônicos . Uma pesquisa sobre a complexidade do circuito aritmético pode ser encontrada em http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

Noam
fonte

11

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$ . O limite inferior de Jerrum-Snir funciona desde que o circuito satisfaça a propriedade de que os monômios formais da raiz são iguais aos monômios diferentes de zero do polinômio calculado.

Ramprasad

1

Acho que este artigo responde diretamente à sua pergunta.

O cancelamento é exponencialmente poderoso para calcular o determinante

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

Thatchaphol
fonte

Cancelamento e determinante

Respostas: