|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Формульная сложность линейной функции в k-арном базисестатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКДата последнего поиска статьи во внешних источниках: 3 марта 2021 г.
- Автор: Сергеев И.С.
- Журнал: Математические заметки
- Том: 109
- Номер: 3
- Год издания: 2021
- Издательство: МИАН
- Местоположение издательства: Москва
- Первая страница: 419
- Последняя страница: 435
- DOI: 10.4213/mzm12802
- Аннотация: В работе предлагается способ расширения метода Храпченко нижней оценки сложности бинарных формул на формулы в k-арных базисах. Полученное расширение позволяет сложность линейной булевой функции и функции голосования n переменных при реализации формулами в базисе из всех k-местных монотонных функций и отрицания оценить как Ω(n^g(k)), где g(k)=1+Θ(1/ln k). Для линейной функции оценка сложности в таком виде неулучшаема. При k=3 доказывается более аккуратная нижняя оценка Ω(n^1.53).
- Добавил в систему: Сергеев Игорь Сергеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | MatZametki_2021.pdf | 535,4 КБ | 4 мая 2022 [isserg] |