Об аддитивной сложности некоторых числовых последовательностей
И. С. Сергеев Научно-исследовательский институт "Квант", г. Москва
Аннотация:
В работе представлено несколько результатов о сложности вычислений
в модели векторных аддитивных цепочек. Получено уточнение верхней
оценки Н. Пиппенджера сложности класса целочисленных
$m \times n$
матриц с ограничением
$q$ на размер коэффициентов при
$H=mn\log_2
q \to \infty$ до
$\min\{m,n\}\log_2 q+(1+o(1))H/\log_2 H+n$.
Асимптотически точно установлена сложность вычисления числа
$2^n-1$ в базисе из степеней двойки: она равна
$(2+o(1))\sqrt n$.
На основе обобщенных последовательностей Сидона построены
конструктивные примеры числовых множеств мощности
$n$: с полиномиальным размером элементов, имеющие сложность
$n+\Omega(n^{1-\varepsilon})$ при любом
$\varepsilon>0$, с размером элементов
$n^{O(\log n)}$, имеющие сложность
$n+\Omega(n)$.
Библиография: 15 названий.
Ключевые слова:
аддитивные цепочки, вентильные схемы, множества Сидона,
${\mathcal
B}_k$-множества, суммы множеств, множества, свободные от сумм,
циклы в графах, нижние оценки сложности.
УДК:
519.71 Поступило: 12.04.2023
Исправленный вариант: 11.07.2023
DOI:
10.4213/mzm13984