Deje ser un campo. Como de costumbre, para una definimos como la complejidad lineal de sobre . Sea el conjunto de monomios de , es decir, los monomios que aparecen en con coeficiente distinto de cero.
¿Es cierto que ?
¿ Se conoce incluso un límite superior más débil para ?
Nota: Esta es una expansión de un comentario anterior, ya que el OP solicitó explícitamente límites superiores más débiles.
El grado total del polinomio está delimitado por ya que cada operación puede duplicar como máximo el grado del polinomio. Por lo tanto, para cada , .f 2L(f) m∈M deg(m)≤2L(f)
Ahora, para algunas variables grados , hay un SLP que calcula por exponenciación binaria si el tamaño es como máximo . Para un monomio , se puede calcular por separado cada y luego tomar su producto. Por lo tanto, donde es el grado total de (que es, por supuesto, un límite superior en cada ).x d xd 2log(d) m=xd11⋯xdnn xdii L(m)≤2nlog(d)+(n−1) d m di
Juntos, se obtiene para :m∈M
Como , uno puede concluirn≤L(f)+1
Observaciones El límite como se indica es muy duro. En particular, el límite superior en dado es que el segundo párrafo no es ajustado. Sin embargo, la respuesta de domotorp muestra que no se puede esperar un límite mucho mejor, y más precisamente que la dependencia cuadrática de no se puede eliminar. Para apretar la construcción, uno podría usar las construcciones más conocidas en las cadenas de adición . Tenga en cuenta que todavía no se conocen los límites precisos para este problema.L(m) L(f)
fuente