Пусть - некоторое поле. Как обычно, для f ∈ k [ x 1 , x 2 , … , x n ] мы определяем L ( f ) как прямолинейную сложность f над k . Пусть F - множество мономов f , а именно мономов, которые появляются в f с ненулевым коэффициентом.
Верно ли , что ?
Даже некоторая более слабая верхняя оценка для известна?
cc.complexity-theory
algebraic-complexity
arithmetic-circuits
Горав Джиндал
источник
источник
Примечание. Это расширение предыдущего комментария, поскольку ОП явно просил более слабые верхние границы.
Полная степень многочлена ограничена поскольку каждая операция может не более чем удваивать степень многочлена. Таким образом, для каждого , .f 2L(f) m∈M deg(m)≤2L(f)
Теперь для некоторой переменной и степени существует SLP, вычисляющая помощью двоичного возведения в степень, если размер не больше . Для мономиального , можно отдельно вычислить каждый , а затем принять их продукт. Таким образом, где - общая степень (которая, конечно, является верхней границей для каждого ).x d xd 2log(d) m=xd11⋯xdnn xdii L(m)≤2nlog(d)+(n−1) d m di
Вместе получаем для :m∈M
Поскольку , можно заключитьn≤L(f)+1
Замечания. Граница, как указано, очень грубая. В частности, верхняя граница дается второй пункт не плотно. Тем не менее, ответ domotorp показывает, что нельзя надеяться на гораздо лучшую оценку, а точнее, что квадратичная зависимость от не может быть удалена. Чтобы затянуть конструкцию, можно использовать самые известные конструкции на цепях сложения . Обратите внимание, что точные границы до сих пор не известны для этой проблемы.L(m) L(f)
источник