Os circuitos aritméticos são mais fracos que os booleanos?

Seja o tamanho mínimo de um circuito aritmético (não monótono) ( + , × , - ) que computa um dado polinômio multilinear f ( x 1 , … , x n ) = ∑ e ∈ E c e n ∏ i = 1 x e i$A(f)$$(+,\times,-)$ e B ( f ) denotam o tamanho mínimo de umcircuitobooleano(não monótono) ( ∨ , ∧ , ¬ ) que computa aversão booleana f b de f definida por: f b ( x 1 , … , x n ) = ⋁ e ∈ E ⋀ i : e i ≠ 0 x

$$f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,$$ $B(f)$$(\lor,\land,\neg)$ $f_b$$f$ $$f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,.$$

Os polinômios conhecidos por qual B ( f ) é menor que A ( f ) ? $f$$B(f)$$A(f)$

$(-)$$(\neg)$$B(f)$$A(f)$$f$$K_n$$B(f)=O(n^3)$$A(f)=2^{\Omega(n)}$$A(f)$

---

NOTA (2016/03/15) Na minha pergunta, eu não especificou como grandes coeficientes são permitidos. Igor Sergeev lembrado me que, por exemplo, o seguinte (univariada) polinomial f ( z ) = Σ m j = 1 2 2 j m z j tem Um ( f ) = Ω ( m 1 / 2 ) (Strassen e pessoas do seu grupo). Mas B ( f ) = 0 para este polinômio, uma vez que f b$c_e$$f(z)=\sum_{j=1}^m 2^{2^{jm}} z^j$$A(f)=\Omega(m^{1/2})$$B(f)=0$ . Podemos obter do fron f ummultivariadapolinomial f ' ( x 1 , ... , x n ) de N = log m variáveis utilizando utilizando a substituição de Kronecker. Associe-se a todo expoente j a monomial X j = ∏ i : a i = 1 x i , onde ( a 1 , … , a n$f_b(z)=z$$f$$f'(x_1,\ldots,x_n)$$n=\log m$$j$$X_j=\prod_{i:a_i=1}x_i$$(a_1,\ldots,a_n)$são os coeficientes 0-1 da representação binária de . Em seguida, o polinómio é desejada f ' = Σ m j = 1 c j X j , e temos que A ( f ' ) + n ≥ Um ( f ) = Ω ( m 1 / 2 ) = 2 Ω ( n ) . Mas a versão booleana de f ' é apenas um OR de variáveis, então B $j$$f'=\sum_{j=1}^m c_j X_j$ $$A(f')+n\geq A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.$$ $f'$ , e temos uma diferença exponencial uniforme. Assim, se a magnitude dos coeficientes puder ser triplo-exponencial no número n de variáveis, o intervalo A ( f ) / B ( f ) podeser mostrado como exponencial. (Na verdade, não a magnitude em si - mais a dependência algébrica dos coeficientes.) É por isso que o verdadeiro problema com A ( f ) é o caso depequenoscoeficientes (idealmente, apenas 0-1). Mas neste caso, como Josué lembrou, o limite inferior A ( f $B(f')\leq n-1$$n$$A(f)/B(f)$ $A(f)$ de Strassen e Baur (com coeficientes 0-1) continua sendo o melhor que temos hoje.$A(f)=\Omega(n\log n)$

$\mathsf{VP}^0 \neq \mathsf{VNP}^0$

$\Omega(n \log n)$$\sum_{i=1}^n x_i^n$$\Omega(n \log n)$$x_1 \vee x_2 \vee \dotsb \vee x_n$