И. С. Сергеев, “Нижняя оценка монотонной контактной сложности пороговой функции $T_n^{n-1}$”, Дискрет. матем., 2023, том 35, выпуск 4,страницы 126

Нижняя оценка монотонной контактной сложности пороговой функции $T_n^{n-1}$

И. С. Сергеев

ФГУП «НИИ «Квант»

Аннотация: Доказано, что сложность вычисления пороговой симметрической функции $T_n^{n-1}$ монотонными контактными схемами равна $\Omega(n \log \log n)$.

Ключевые слова: контактные схемы, пороговые функции, монотонные вычисления.

УДК: 519.714.4

Статья поступила: 20.08.2023

DOI: 10.4213/dm1789