Прямая сложность мономов

11

Пусть - некоторое поле. Как обычно, для f k [ x 1 , x 2 , , x n ] мы определяем L ( f ) как прямолинейную сложность f над k . Пусть F - множество мономов f , а именно мономов, которые появляются в f с ненулевым коэффициентом.kfk[x1,x2,,xn]L(f)fkFff

Верно ли , что ?mF:L(m)L(f)

Даже некоторая более слабая верхняя оценка для известна?L(m)

Горав Джиндал
источник

Ответы:

13

f=(Σi=1nxi)2n
(2n+n1n1)2n2L(f)=O(n)2O(nlogn)O(n)fmL(m)=Ω~(L2(f))
domotorp
источник
2
В качестве небольшого конструктивного примера, основанного на ответе домоторпа, можно взять с а . f=(x+y)8L(f)=4L(x7y)=L(x7)+1=5
Бруно
@domotorp, спасибо за хороший ответ. Кажется ли это также верхней границей? Или может быть лучше нижние границы?
Горав Джиндал
Я не знаю, но так как этот пример был настолько прост, я бы предположил, что разрыв может быть больше, возможно, даже экспоненциальным.
domotorp
1
У меня есть «доказательство», что существует линейная верхняя граница ... Где я ошибаюсь (так как вы доказали квадратичную нижнюю оценку)? Она заключается в следующем: С SLP размера , то вычислить многочлен общей степени . Теперь имеет SLP размером не более с бинарным возведением в степень. Тогда моном с степенью вариации имеет размер SLP не более (очень грубая граница): вычислите все , , а затем их произведение. Таким образом, если мы рассмотрим многочлен , его полная степень не больше , и каждый моном имеет SLP размером не болееL2LxD2logDD n2nlogD+n1xiDiDiDf2L(f)2nL(f)+n1,
Бруно
1
@ Бруно: Хорошее доказательство, и в этом нет ничего плохого, но оно не линейное, так как вы умножаете и . Но поскольку мы знаем, что может зависеть не более чем от переменных, мы можем принять , что подразумевает требуемую квадратичную оценку. Таким образом, . nL(f)fL(f)+1nL(f)+1L(m)=O(L2(f))
Domotorp
8

Примечание. Это расширение предыдущего комментария, поскольку ОП явно просил более слабые верхние границы.

Полная степень многочлена ограничена поскольку каждая операция может не более чем удваивать степень многочлена. Таким образом, для каждого , .f2L(f)mMdeg(m)2L(f)

Теперь для некоторой переменной и степени существует SLP, вычисляющая помощью двоичного возведения в степень, если размер не больше . Для мономиального , можно отдельно вычислить каждый , а затем принять их продукт. Таким образом, где - общая степень (которая, конечно, является верхней границей для каждого ).xdxd2log(d)m=x1d1xndnxidiL(m)2nlog(d)+(n1)dmdi

Вместе получаем для : mM

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

Поскольку , можно заключить nL(f)+1

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

Замечания. Граница, как указано, очень грубая. В частности, верхняя граница дается второй пункт не плотно. Тем не менее, ответ domotorp показывает, что нельзя надеяться на гораздо лучшую оценку, а точнее, что квадратичная зависимость от не может быть удалена. Чтобы затянуть конструкцию, можно использовать самые известные конструкции на цепях сложения . Обратите внимание, что точные границы до сих пор не известны для этой проблемы.L(m)L(f)

Bruno
источник