О сложности монотонных схем для пороговых симметрических булевых функцийстатья

Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 29 июля 2020 г.

Работа с статьей


[1] Сергеев И. С. О сложности монотонных схем для пороговых симметрических булевых функций // Дискретная математика. — 2020. — Т. 32, № 1. — С. 81–109. Показано, что сложность реализации монотонной симметрической булевой функции n переменных с порогом k=O(1) схемами над базисом {∨,∧} не превосходит 2(log k)n+o(n). Кроме того, доказано, что сложность функции с порогом 2 равна 2n+Θ(sqrt n), а сложность функции с порогом 3 равна 3n+O(log n) — установлены соответствующие нижние оценки. [ DOI ]

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть