À luz do resultado recente do abismo na profundidade 3 (que, entre outras coisas, produz profundidade-3 circuito aritmético para onxndeterminante sobreC), que têm as seguintes questões: Grigoriev e Karpinskirevelouum2Ω(n)um limite inferior para qualquer profundidade-3 circuito aritmético de computação o determinante denxnmatrizes sobre campos finitos (o que eu acho, também vale para o Permanente). A fórmula de Ryserpara calcular o Permanent fornece um circuito aritmético de profundidade 3 do tamanhoO(n22n)=2O( . Isso mostra que o resultado é essencialmente rígido para os circuitos de profundidade 3 para os campos permanentes sobre finitos. Eu tenho duas perguntas:
1) Existe uma fórmula de profundidade 3 para o determinante análogo à fórmula de Ryser para o Permanente?
2) Um limite inferior no tamanho dos circuitos aritméticos que calculam o polinômio determinante \ textit {sempre} gera um limite inferior para o polinômio Permanente? (Acima de eles são os mesmos polinômios).
Embora minha pergunta atual seja sobre esses polinômios em campos finitos, eu também gostaria de saber o status dessas perguntas em campos arbitrários.
Respostas:
O Permanent é completo para o VNP sob projeções p sobre qualquer campo não da característica 2. Isso fornece uma resposta positiva para sua segunda pergunta. Se essa redução fosse linear, daria uma resposta positiva à sua primeira pergunta, mas acredito que isso permanece em aberto.
Em mais pormenor: há alguns polinómio de tal modo que d e t n ( X ) é uma projecção de p e r m q ( n ) ( Y ) , ou seja, há um certo substituição envio de cada variável y i j tanto a uma variável x k ℓ ou a uma constante tal que após essa substituição a permanente q ( n ) × q ( n ) esteja computando nq(n) detn(X) permq(n)(Y) yij xkℓ q(n)×q(n) determinante.n×n
1) Assim, a fórmula de Ryser produz uma fórmula de profundidade 3 (a profundidade não aumenta sob as projeções, porque as substituições podem ser feitas nas portas de entrada) do tamanho para determinante. ATUALIZAÇÃO : Como @Ramprasad aponta nos comentários, isso só fornece algo não trivial se q ( n ) = o ( n log n ) , pois existe uma fórmula trivial de profundidade 2 do tamanho n ⋅ n ! = 2 O ( n log n )2O(q(n)) q(n)=o(nlogn) n⋅n!=2O(nlogn) para det. Estou com Ramprasad, pois o melhor que conheço é a redução através de ABPs, o que gera .q(n)=O(n3)
2) Se a permanente pode ser calculada - novamente, sobre algum campo de característica não 2 - por um circuito do tamanho s ( m ) , então n × n determinante pode ser calculado por um circuito do tamanho s ( q ( n ) ) . Portanto, um limite inferior de b ( n ) no tamanho do circuito para d e t n produz um limite inferior de b ( q - 1 ( n ) ) no tamanho do circuito para o permanente (isto ém×m s(m) n×n s(q(n)) b(n) detn b(q−1(n)) inverso, não 1 / q ( nq ). O acima mencionado q ( n ) = O ( n 3 ) produz um b ( n 1 / 3 ) perm limite inferior de uma b ( n ) Det limite inferior.1/q(n) q(n)=O(n3) b(n1/3) b(n)
fonte
It is very possible that the determinant is, in a way, harder than the permanent. They are both polynomials, the Waring Rank(sums of n powers of linear forms) of the permanent is roughly 4^n, Chow Rank(sums of products of linear forms) is roughly 2^n. Clearly, Waring Rank \leq 2^{n-1} Chow Rank. For the determinant, those numbers are just lower bounds. On the other hand, I proved a while ago that the Waring rank of the determinant is upper bounded by (n+1)! and this might be close to the truth.
fonte