Complexidade linear de monômios

11

Seja k algum campo. Como sempre, para um fk[x1,x2,,xn] , definimos L(f) como a complexidade linear de f sobre k . Seja F o conjunto de monômios de f , ou seja, os monômios que aparecem em f com coeficiente diferente de zero.

É verdade que mF:L(m)L(f) ?

Mesmo algum limite superior mais fraco para L(m) é conhecido?

Gorav Jindal
fonte

Respostas:

13

Se , então ele tem monomios e . Por um argumento de contagem, existem programas lineares de comprimento . Como tem mais monômios, para alguns precisamos de um programa mais longo. De fato, este argumento fornece um monômio para o qual .

f=(Σi=1nxi)2n
(2n+n1n1)2n2L(f)=O(n)2O(nlogn)O(n)fmL(m)=Ω~(L2(f))
domotorp
fonte
2
Como um pequeno exemplo construtivo baseado na resposta de domotorp, pode-se tomar com enquanto . f=(x+y)8L(f)=4L(x7y)=L(x7)+1=5
Bruno
@domotorp, obrigado pela resposta agradável. Este também parece ser o limite superior? Ou pode haver limites inferiores melhores?
Gorav Jindal
Não sei, mas como esse exemplo era tão simples, acho que a diferença pode ser maior, possivelmente até exponencial.
Domotorp #
1
Eu tenho uma "prova" de que existe um limite superior linear ... Onde estou errado (desde que você provou um limite inferior quadrático)? É como segue: Com uma SLP de tamanho , você calcula um polinômio do total grau . Agora tem um SLP de tamanho no máximo com exponenciação binária. Um degree- -variate monomial foi, em seguida, um SLP de tamanho no máximo (muito áspero ligado): calcular todos os , , e, em seguida, o seu produto. Assim, se considerarmos um polinômio , seu grau total é no máximo , e cada monômio tem uma SLP de tamanho no máximoL2LxD2logDD n2nlogD+n1xiDiDiDf2L(f)2nL(f)+n1.
de Bruno
1
@Bruno: prova agradável e não há nada de errado com ele, mas não é linear, como você multiplicar e . Mas como sabemos que pode depender de no máximo variáveis , podemos assumir , o que implica o limite quadrático necessário. Assim, . nL(f)fL(f)+1nL(f)+1L(m)=O(L2(f))
Domotorp #
8

Nota: Esta é uma expansão de um comentário anterior, uma vez que o OP solicitou explicitamente limites superiores mais fracos.

O grau total de polinômio é delimitado por pois cada operação pode no máximo dobrar o grau do polinômio. Assim, para cada , .f2L(f)mMdeg(m)2L(f)

Agora, para algumas variáveis grau , existe um SLP que computa por exponenciação binária se o tamanho for no máximo . Para um monômio , pode-se calcular separadamente cada e depois levar o produto. Assim, onde é o grau total de (que é obviamente um limite superior em cada ).xdxd2log(d)m=x1d1xndnxidiL(m)2nlog(d)+(n1)dmdi

Juntos, obtém-se para : mM

L(m)2nlog(deg(m))+(n1)2nL(f)+(n1).

Como , pode-se concluir nL(f)+1

mM,L(m)2L(f)2+3L(f).

Observações O limite conforme indicado é muito difícil. Em particular, o limite superior de dado no segundo parágrafo não é rígido. No entanto, a resposta de domotorp mostra que não se pode esperar uma ligação muito melhor, e mais precisamente que a dependência quadrática de não pode ser removida. Para reforçar a construção, pode-se usar as construções mais conhecidas em cadeias de adição . Observe que os limites precisos ainda não são conhecidos para esse problema.L(m)L(f)

Bruno
fonte