Sea el tamaño mínimo de un circuito aritmético (no monótono) ( + , × , - ) que calcula un polinomio multilineal dado f ( x 1 , … , x n ) = ∑ e ∈ E c e n ∏ i = 1 x e i i y B ( f ) denota el tamaño mínimo de uncircuitobooleano(no monótono) ( ∨ , ∧ , ¬ ) que calcula laversión booleana f b de f definida por: f b ( x 1 , … , x n ) = ⋁ e ∈ E ⋀ i : e i ≠ 0 x i
¿Se conocen los polinomios para los cuales B ( f ) es más pequeño que A ( f ) ?
Si consideramos versiones monótonas de circuitos, sin puertas Minus y sin Not ( ¬ ) , entonces B ( f ) puede ser incluso exponencialmente más pequeño que A ( f ) : tome, por ejemplo, el polinomio de ruta st más corto f en K n ; entonces B ( f ) = O ( n 3 ) y A ( f ) = 2 Ω ( n . Pero, ¿qué sucede en el "mundo no monótono"? Por supuesto,no se pueden conocergrandesbrechas solo porque no tenemos grandes límites inferiores enA(f). ¿Pero quizás hay al menos algunas brechas pequeñas conocidas?
NOTA (15.03.2016) En mi pregunta, no especifiqué cuán grandes coeficientes están permitidos. Igor Sergeev me recordarse que, por ejemplo, los siguientes (univariado) polinomio f ( z ) = Σ m j = 1 2 2 j m z j tiene A ( f ) = Ω ( m 1 / 2 ) (Strassen y la gente de su grupo). Pero B ( f ) = 0 para este polinomio, ya que f b ( . Podemos obtener desde f unpolinomiomultivariado f ' ( x 1 , ... , x n ) de n = log m variables usando la sustitución de Kronecker. Asociar con cada exponente j un monomio X j = ∏ i : a i = 1 x i , donde ( a 1 , … , a n )son los coeficientes 0-1 de la representación binaria de . A continuación, el polinomio se desea f ' = Σ m j = 1 c j X j , y tenemos que A ( f ' ) + n ≥ A ( f ) = Ω ( m 1 / 2 ) = 2 Ω ( n ) . Pero la versión booleana de f ' es solo un OR de variables, entonces B (