Complexidade de circuitos aritméticos monotônicos de polinômios simétricos elementares?

O ésimo polinômio simétrico elementar é a soma de todos os produtos de variáveis distintas. Estou interessado na complexidade aritmética monotônica desse polinômio. Um algoritmo de programação dinâmica simples (assim como a Fig. 1 abaixo) fornece um circuito com portas . $k$ $S_k^n(x_1,\ldots,x_n)$ $\binom{n}{k}$ $k$ $(+,\times)$ $(+,\times)$ $O(kn)$

Pergunta: Um limite inferior de $\Omega(kn)$ conhecido?

Um circuito $(+,\times)$ é inclinado se pelo menos uma das duas entradas de cada porta do produto for uma variável. Esse circuito é realmente o mesmo que a rede de comutação e retificação (um gráfico acíclico direcionado com algumas arestas rotuladas por variáveis; cada caminho st fornece o produto de suas etiquetas e a saída é a soma de todos os caminhos st). Já há 40 anos, Markov provou um resultado surpreendentemente apertado: um circuito aritmético monotônico mínimo para $S_k^n$ tem exatamente $k(n-k+1)$ portas de produto. O limite superior segue da Fig. 1:

Mas não vi nenhuma tentativa de provar um limite tão baixo para circuitos não inclinados. É apenas nossa "arrogância" ou há algumas dificuldades inerentes observadas ao longo do caminho?

PS: Eu sei que as portas $\Omega(n\log n)$ são necessárias para calcular simultaneamente todos os $S_1^n,\ldots,S_n^n$ . Isso segue do limite inferior do tamanho dos circuitos booleanos monótonos que classificam a entrada 0-1; veja a página 158 do livro de Ingo Wegener . A rede de classificação da AKS também implica que as portas $O(n\log n)$ sejam suficientes nesse caso (booleano). Na verdade, Baur e Strassen provaram um vinculado $\Theta(n\log n)$ ao tamanho do circuito aritmético não monótono para $S_{n/2}^n$ . Mas e os circuitos aritméticos monótonos ?

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits dynamic-programming Stasys
fonte

Um desafio é que, se você remover a restrição "monótona", nós não sabemos como calcular essas coisas de forma eficiente. Você pode calcular o valor de todos os (avaliar todos os polinômios simétricos elementares) em , usando a multiplicação polinomial baseada em FFT. Portanto, provar um limite inferior de no modelo de circuito monotônico exigiria provar um limite inferior de na multiplicação polinomial. $S_0^n,\dots,S_n^n$ $n+1$ $O(n \log^2 n)$ $\Omega(nk)$ $\Omega(n^2)$

Aqui está como. Introduza um formal desconhecido e considere o polinômio $y$

P (y) = \prod_{Eu = 1}^{n} (1 + x_{Eu} y) .

$P(y) = \prod_{i=1}^n (1 + x_i y).$

Observe que, como os são constantes conhecidas, este é um polinômio univariado com desconhecido e com grau . Agora você pode observar que o coeficiente de em é exatamente , portanto, para avaliar todos os , basta calcular . $x_i$ $y$ $n$ $y^k$ $P(y)$ $S_k^n$ $S_0^n,\dots,S_n^n$ $P(y)$

Isso torna possível calcular em tempo: construa uma árvore binária equilibrada de polinômios com o nas folhas e multiplique os polinômios. Multiplicar dois polinômios de grau leva tempo usando técnicas de FFT, obtemos a recorrência , que resolve . Por conveniência, estou ignorando os fatores . $P(y)$ $O(n \lg^2 n)$ $(1+x_i y)$ $d$ $O(d \lg d)$ $T(n) = 2 T(n/2) + O(n \lg n)$ $T(n) = O(n \lg^2 n)$ $\text{poly}(\lg \lg n)$

Se você se importa com o caso em que é muito pequeno, pode computar no tempo usando truques semelhantes, lembrando que você só se preocupa com (isto é, jogando fora todos os termos de ou potências superiores de ). $k$ $S_0^n,\dots,S_k^n$ $O(n \lg^2 k)$ $P(x) \bmod y^{k+1}$ $y^{k+1}$ $y$

Obviamente, a FFT usa subtração, de forma ingênua que não é expressável em um circuito monótono. Não sei se há outra maneira de multiplicar polinômios de maneira eficiente com circuitos aritméticos monotônicos, mas qualquer método monotônico eficiente para multiplicação de polinômios também leva imediatamente a um algoritmo para o seu problema. Portanto, limites inferiores no seu problema exigem / implicam limites inferiores para multiplicação polinomial.

DW
fonte

DW, obrigado por recordar esta construção! Geralmente é atribuído a Ben-Or, e eu deveria ter mencionado. A construção também fornece uma <i> fórmula </i> de tamanho e profundidade apenas (!) o operador (avaliando em algum ponto pontos). Isso foi usado para separar fórmulas homogêneas e não homogêneas de pequena profundidade. Mas, como você mencionou, a construção usa substancialmente subtração. Então, minha pergunta é: quão "substancial" é esse uso? Isso pode ser interessante também no cenário de profundidade restrita.

O (n^{2})

$O(n^2)$

3

$3$

S_{0}^{n}, \dots, S_{n}^{n}

$S_0^n,\ldots,S_n^n$

P (y)

$P(y)$

n + 1

$n+1$

Stasys

@Stasys: Eu acho que subtração é bastante crucial. Viz. o limite inferior de Nisan-Wigderson em circuitos homogêneos de profundidade 3 ; em circuitos homogêneos de profundidade 3, o ponto é que é inútil calcular termos cujos graus diferem do grau da saída. Portanto, isso limita os tipos de cancelamentos que podem acontecer. Enquanto na construção Ben-Or, para calcular , é preciso calcular um polinômio de grau (mesmo que a saída tenha grau ) e, em seguida, usar crucialmente o cancelamento para se livrar dos termos de graus . Esta não é uma prova, apenas alguma intuição ...

S_{k}^{n}

$S_k^n$

n

$n$

k < n

$k < n$

> k

$> k$

Joshua Grochow

@ Josué: sim, sabemos que os coeficientes da variável no polinômio são exatamente os polinômios . Mas precisamos de Gauss (e subtrações) para extrair esses coeficientes de valores de em pontos distintos. Minha pergunta pergunta se a "palavra monótona" não tem Gauss , de fato , neste caso. (Com uma resposta adivinhada - NÃO.) Não tenho certeza de que, para isso, basta eliminar os termos de graus . Temos que encontrar esses primeiros coeficientes.

y

$y$

P (y, x)

$P(y,x)$

S_{k}^{n} (x)

$S_k^n(x)$

n + 1

$n+1$

P (y)

$P(y)$

n + 1

$n+1$

> k

$> k$

k

$k$

Stasys

Complexidade de circuitos aritméticos monotônicos de polinômios simétricos elementares?

Respostas: