¿Son los circuitos aritméticos más débiles que los booleanos?

12

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 iA(f)(+,×,) 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 i0 x i

f(x1,,xn)=eEcei=1nxiei,
B(f)(,,¬) fbf
fb(x1,,xn)=eE i:ei0xi.
¿Se conocen los polinomios para los cuales B ( f ) es más pequeño que A ( f ) ? fB(f)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()(¬)B(f)A(f)fKnB(f)=O(n3) . 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? A(f)=2Ω(n)A(f)


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 (cef(z)=j=1m22jmzjA(f)=Ω(m1/2)B(f)=0 . 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 )fb(z)=zff(x1,,xn)n=logmjXj=i:ai=1xi(a1,,an)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 (jf=j=1mcjXj
A(f)+nA(f)=Ω(m1/2)=2Ω(n).
f , y tenemos una brecha exponencial par. Por lo tanto, si la magnitud de los coeficientes puede ser triple exponencial en el número n de variables, entoncessepuede demostrar quela brecha A ( f ) / B ( f ) es incluso exponencial. (En realidad, no la magnitud en sí, más la dependencia algebraica de los coeficientes). Es por eso que el verdadero problema con A ( f ) es el caso deloscoeficientespequeños(idealmente, solo 0-1). Pero en este caso, como recordó Joshua, el límite inferior A ( f )B(f)n1nA(f)/B(f) A(f) de Strassen y Baur (con coeficientes 0-1) sigue siendo lo mejor que tenemos hoy.A(f)=Ω(nlogn)

Stasys
fuente

Respuestas:

9

VP0VNP0

Ω(nlogn)i=1nxinΩ(nlogn)x1x2xn

Joshua Grochow
fuente
Hola Joshua: tienes razón, ¡permanente es un ejemplo (aunque condicional)! Bueno, no conocemos ningún límite inferior en A (f) para permanente. Pero si las versiones libres de constantes de VP y VNP difieren, entonces conocemos la separación B (f) frente a A (f) sin conocer un límite (real).
Stasys
2
Ω(nlogn)
1
a Joshua: correcto, buen punto de nuevo. Si f es una suma de n-ésimas potencias de todas las n variables individuales, entonces B (f) es como máximo n, y Baur-Strassen muestra que A (f) es al menos aproximadamente n veces el logaritmo de n. Este es el más conocido por A (f). Entonces, la brecha explícita más grande conocida para mi pregunta es de hecho solo logarítmica. (Una pregunta a un lado: ¿sabes por qué mi @ siempre desaparece en los comentarios?)
Stasys
@Stasys: Buen ejemplo. (Re: aparte. No lo creo. Creo que el sistema hace una inferencia automática de a quién están "dirigidas" las cosas, y si está dirigiendo un mensaje a la "persona predeterminada", entonces lo elimina. Creo .)
Joshua Grochow
Correcto. El autor de una publicación siempre recibe notificaciones de nuevos comentarios, por lo que el sistema elimina la notificación explícita @ como redundante.
Emil Jeřábek