Дискрет. матем.,
2023, том 35, выпуск 4, страницы 126–131
(Mi dm1789)
|
Нижняя оценка монотонной контактной сложности пороговой функции $T_n^{n-1}$
И. С. Сергеев ФГУП «НИИ «Квант»
Аннотация:
Доказано, что сложность вычисления пороговой симметрической функции
$T_n^{n-1}$ монотонными контактными схемами равна
$\Omega(n \log \log n)$.
Ключевые слова:
контактные схемы, пороговые функции, монотонные вычисления.
УДК:
519.714.4 Статья поступила: 20.08.2023
DOI:
10.4213/dm1789
© , 2026
Полный текст:
PDF файл (504 kB)