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

12

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

f(x1,,xn)=eEcei=1nxiei,
B(f)(,,¬) fbf
fb(x1,,xn)=eE i:ei0xi.
Os polinômios conhecidos por qual B ( f ) é menor que A ( f ) ? fB(f)A(f)

()(¬)B(f)A(f)fKnB(f)=O(n3)A(f)=2Ω(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 (cef(z)=j=1m22jmzjA(f)=Ω(m1/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 )fb(z)=zff(x1,,xn)n=logmjXj=i:ai=1xi(a1,,an)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 (jf=j=1mcjXj
A(f)+nA(f)=Ω(m1/2)=2Ω(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)n1nA(f)/B(f) A(f) de Strassen e Baur (com coeficientes 0-1) continua sendo o melhor que temos hoje.A(f)=Ω(nlogn)

Stasys
fonte

Respostas:

9

VP0VNP0

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

Joshua Grochow
fonte
Oi Joshua: você está certo, permanente é um exemplo (embora condicional)! Bem, não conhecemos nenhum limite inferior em A (f) para permanente. Mas se as versões livres de constante do VP e VNP diferem, então conhecemos a separação B (f) vs. A (f) sem conhecer um limite (real).
Stasys
2
Ω(nlogn)
1
em Josué: certo, bom argumento novamente. Se f é a soma das n-ésimas potências de todas as n variáveis ​​únicas, então B (f) é no máximo n, e Baur-Strassen mostra que A (f) é pelo menos n vezes logaritmo de n. Este é o mais conhecido por A (f). Portanto, a maior lacuna explícita conhecida para minha pergunta é de fato apenas logarítmica. (A questão de lado: você sabe por que o meu @ sempre desaparece nos comentários?)
Stasys
@Stasys: Bom exemplo. (Re: aparte. Eu não. Acho que o sistema faz alguma inferência automática de quem as coisas são "respondidas" e, se você estiver direcionando uma mensagem para a "pessoa padrão", ela será removida. .)
Joshua Grochow 14/03
Certo. O autor de uma postagem é sempre notificado sobre novos comentários, portanto, o sistema remove a notificação @ explícita como redundante.
Emil Jeřábek 3,0