Веса точных пороговых функций
Л. Бабаиa,
К. А. Хансенb,
В. В. Подольскийcd,
Сяомин Сюнe a University of Chicago, USA
b University of Aarhus, Denmark
c Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
d Национальный исследовательский университет "Высшая школа экономики", г. Москва
e Institute of Computing Technology, Chinese Academy of Sciences, China
Аннотация:
Мы рассматриваем точные пороговые булевы функции, задаваемые линейными уравнениями, и, в более общем виде, многочленами степени
$d$. Мы доказываем верхние и нижние оценки на величину (абсолютное значение) коэффициентов, необходимых для реализации таких функций. Эти оценки очень близки друг к другу. В частности, в линейном случае они почти совпадают. Рассматриваемая величина совпадает с максимальной величиной целых коэффициентов линейного уравнения, необходимой для задания любого возможного пересечения гиперплоскости в
$\mathbb R^n$ с булевым кубом
$\{0,1\}^n$ и, в общем случае, пересечения гиперповерхности степени
$d$ в
$\mathbb R^n$ и булевого куба
$\{0,1\}^n$. В процессе доказательства мы строим новое семейство плохо обусловленных матриц. Мы также рассматриваем вариант задачи (в линейном случае) с дополнительным параметром размерности
$k$ аффинного подпространства, порождаемого решениями, и доказываем верхние и нижние оценки также и в этом случае. Эти оценки в терминах
$k$ имеют существенный зазор, что составляет предмет дальнейших исследований.
Библиография: 33 наименования.
Ключевые слова:
сложность вычислений, булевы функции, пороговые функции, полиномиальные пороговые функции, анти-адамаровы матрицы.
УДК:
519.1
MSC: 06E30 Поступило в редакцию: 02.10.2020
Исправленный вариант: 02.03.2021
DOI:
10.4213/im9113