Les circuits arithmétiques sont-ils plus faibles que booléens?

Soit la taille minimale d'un circuit arithmétique (non monotone) calculant un polynôme multilinéaire et désignent la taille minimale d'un circuit booléen (non monotone) calculant la version booléenne de défini par: $A(f)$$(+,\times,-)$

$$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\,.$$

Les polynômes connus pour lesquels est plus petit que ? $f$$B(f)$$A(f)$

Si nous considérons des versions monotones des circuits - pas de portes Moins et Pas - alors peut même être exponentiellement plus petit que : prenez, par exemple, le polynôme le plus court du chemin st sur ; alors et . Mais que se passe-t-il dans le "monde non monotone"? Bien sûr, de grands écarts ne peuvent pas être connus simplement parce que nous n'avons pas de grandes limites inférieures sur . Mais peut-être y a-t-il au moins quelques petites lacunes connues? $(-)$$(\neg)$$B(f)$$A(f)$$f$$K_n$$B(f)=O(n^3)$$A(f)=2^{\Omega(n)}$$A(f)$

---

NOTE (15.03.2016) Dans ma question, je n'ai pas précisé la taille des coefficients autorisés. Igor Sergeev m'a rappelé que, par exemple, le polynôme suivant (univarié) a (Strassen et les gens de son groupe). Mais pour ce polynôme, puisque . Nous pouvons obtenir fron un polynôme multivarié de variables en utilisant la substitution de Kronecker. Associer à chaque exposant un monôme , où$c_e$$f(z)=\sum_{j=1}^m 2^{2^{jm}} z^j$$A(f)=\Omega(m^{1/2})$$B(f)=0$$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)$sont les coefficients 0-1 de la représentation binaire de . Alors le polynôme souhaité est , et nous avons que Mais la version booléenne de n'est qu'un OU de variables, donc , et nous avons même un écart exponentiel. Ainsi, si l'amplitude des coefficients peut être triple exponentielle dans le nombre de variables, alors l'écart peut être montré comme même exponentiel. (En fait, pas la grandeur elle-même - plus la dépendance algébrique des coefficients.) C'est pourquoi le vrai problème avec est le cas des petits$j$$f'=\sum_{j=1}^m c_j X_j$ $$A(f')+n\geq A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.$$ $f'$$B(f')\leq n-1$$n$$A(f)/B(f)$ $A(f)$coefficients (idéalement, seulement 0-1). Mais dans ce cas, comme l'a rappelé Joshua, la borne inférieure de Strassen et Baur (avec des coefficients 0-1) reste la meilleure que nous ayons aujourd'hui.$A(f)=\Omega(n\log n)$

Le permanent semble se qualifier, au moins conditionnellement (c'est-à-dire en supposant ). Notez que la version booléenne du permanent consiste simplement à décider si un graphe biparti donné a une correspondance parfaite, qui a des circuits de taille poly.$\mathsf{VP}^0 \neq \mathsf{VNP}^0$

[Résumant les commentaires ci-dessous:] Bien que cet exemple soit conditionnel, rien de plus qu'un écart logarithmique ne peut être attendu inconditionnellement pour le moment, car est toujours la borne inférieure la plus connue sur les circuits algébriques généraux. Comme l'a souligné Stasys, cet écart logarithmique est atteint par la fonction (nécessite des circuits algébriques de taille par Baur-Strassen), dont la valeur booléenne est la version est juste .$\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$