Seja algum campo. Como sempre, para um , definimos como a complexidade linear de sobre . Seja o conjunto de monômios de , ou seja, os monômios que aparecem em com coeficiente diferente de zero.
É verdade que ?
Mesmo algum limite superior mais fraco para é conhecido?
cc.complexity-theory
algebraic-complexity
arithmetic-circuits
Gorav Jindal
fonte
fonte
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 , .f 2L(f) m∈M deg(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 ).x d xd 2log(d) m=xd11⋯xdnn xdii L(m)≤2nlog(d)+(n−1) d m di
Juntos, obtém-se para :m∈M
Como , pode-se concluirn≤L(f)+1
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)
fonte