Явные полиномы от 1 переменной с нижними границами сложности суперлогарифмической схемы?

Подсчитав аргументы, можно показать, что существуют многочлены степени n от 1 переменной (т. Что-то вроде которые имеют сложность схемы n. Также можно показать, что для многочлена типа требуется как минимум умножений (это нужно просто для получения достаточно высокой степени). Существуют ли явные примеры полиномов от 1 переменной с суперлогарифмической нижней границей сложности? (результаты по любому полю были бы интересны) $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ $x^n$ $\log_2 n$

cc.complexity-theory circuit-complexity polynomials algebraic-complexity Мэтт Гастингс
источник

Есть примеры , вы имеете в виду с схемной сложности над конечным полем? Я не понимаю, как аргумент подсчета работал бы над бесконечным полем, и по рациональным причинам я почти уверен, что граница Патерсона-Стокмейера является жесткой (см. Также мой ответ ниже).

n

$n$

\sqrt{n}

$\sqrt{n}$

Джошуа Грохов

Ограничение sqrt (n), которое вы упомянули, является лишь верхней границей количества умножений (по любому полю), но если мы считаем операции сложения и умножения операциями, то нам нужно n операций над бесконечным полем почти для каждого полинома, просто потому что в многочлене есть n различных коэффициентов, и нет способа оценить все возможные многочлены с менее чем n операциями (я не уверен, следует ли это назвать аргументом подсчета или нет).

Мэтт Гастингс

Я думаю, что вы должны быть немного более точными в утверждении «нет способа оценить все возможные полиномы с числом операций меньше n». Один из способов интерпретации этого заключается в следующем: если мы думаем о многочлене как о многочлене не только по , но и рассматриваем как переменные (или, что эквивалентно, предположим, что алгебраически независимы), то результат, который требует n дополнений, - это Pan (1966), а не просто счетный аргумент (хотя это не так уж сложно). В противном случае, я не совсем уверен, к какому результату вы обращаетесь с этим утверждением.

\sum a_{i} x^{i}

$\sum a_i x^i$

x

$x$

a_{i}

$a_i$

a_{i}

$a_i$

Джошуа Грохов

Я имею в виду: схема состоит из сложения и умножения. Входные данные для данного вентиля могут быть выходами предыдущих вентилей, или x, или некоторых констант. Вопрос в следующем: можем ли мы найти схему и выбор констант в этой схеме для данного полинома? Но у нас есть (n + 1) -мерное пространство полиномов, но если мы зафиксируем структуру схемы с меньшим, чем n вентилями (под «структурой», я имею в виду, какие вентили используют выходы каких других вентилей) и рассмотрим все возможный выбор констант дает меньше n-мерного пространства многочленов, которые можно вычислить.

Мэтт Гастингс

Между прочим, у меня сложилось впечатление, что построение явных примеров над R или C без дополнительных ограничений на коэффициенты в основном решено. С другой стороны, при построении явных примеров, когда все коэффициенты a_i являются целыми числами и не растут слишком быстро, он все еще открыт? Есть пример со всеми целочисленными константами в упомянутом опросе, но они растут вдвое экспоненциально.

Мэтт Гастингс

Патерсон и Стокмейер показывают, что для большинства наборов рациональных чисел оценки требуется арифметика операции, и это жестко. $n$ $(a_1, \dotsc, a_n)$ $\prod_{i=1}^{n} (x - a_i)$ $\Omega(\sqrt{n})$

Следующие полиномы попадают в логарифмический множитель границы по результатам Штрассена, Шнорра и Хайнца и Сивингинга: , , (для рациональное, которое не является целым числом) и т. д. Точные ссылки и более подробно об этом см. на стр. 324-325 опроса фон Цур Гатена . $\sqrt{n}$ $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$ $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$ $\sum_{i=1}^{n} i^{r} x^{i}$ $r$

Джошуа Грохов
источник

Благодарю. Таким образом, может показаться, что открытая проблема заключается в том, что если вы считаете дополнения также операциями, можно ли построить многочлен, для которого требуется больше, чем sqrt (n) операций, с целью создания такового, для которого требуется n операций. Какие-нибудь результаты к этому? (Я сомневаюсь в этом, потому что в методе, который требует только умножения sqrt (n), сложения дают некоторое умножение матриц, и это, вероятно, сводится к нижним пределам сложности умножения матрицы на скаляр)

matt hastings

Явные полиномы от 1 переменной с нижними границами сложности суперлогарифмической схемы?

Ответы: