О числе корней булевых полиномов

 
Код статьиS004446690000344-9-1
DOI10.31857/S004446690000344-9
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Аффилиация: ВЦ РАН ФИЦ «Информатика и управление»
Аффилиация: МГТУ им. Н.Э.Баумана
Адрес: Российская Федерация
Название журналаЖурнал вычислительной математики и математической физики
ВыпускТом 58 Номер 7
Страницы1235-1244
Аннотация

В работе предлагается такой алгоритм на основе свойств матрицы мономов. Для различных типов полиномов приведены точные формулы числа нулей полинома и матожидания числа нулей. Рассматривается подкласс булевых полиномов – полиномы с разделяющимися переменными. Доказан результат, который может рассматриваться как обобщение леммы о рандомизации. Теоретические результаты работы могут служить основой методик оценки применимости полиномов в различных прикладных задачах. Библ. 6.

Ключевые словабулев полином, корни полинома, NP-трудные задачи, лемма о рандомизации
Получено05.09.2018
Дата публикации11.10.2018
Кол-во символов476
Цитировать   Скачать pdf Для скачивания PDF необходимо авторизоваться
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1330

Оценка читателей: голосов 0

1. Сидельников В.М. Открытое шифрование на основе двоичных кодов Рида–Маллера // Дискретная математика. 1994. № 2 (4). С. 3-20.

2. Чижов И.В., Бородин М.А. Уязвимость криптосистемы Мак-Элиса, построенной на основе двоичных кодов Рида–Маллера // Прикладная дискретная математика. Приложение. 2013. № 6. С. 48–49.

3. Мак-Вильямс Дж., Слоэн Н. Теория кодов, исправляющих ошибки. М.: Связь, 1979. 745 с.

4. Леонтьев В.К. Комбинаторика и информация. Часть 1. Комбинаторный анализ. М.: МФТИ, 2015. 174 с.

5. Леонтьев В.К., Морено О. О нулях булевых полиномов // Ж. вычисл. матем. и матем. физ. 1998. Т. 38. № 9. С. 1608–1615.

6. Леонтьев В.К. Симметрические булевы полиномы. // Ж. вычисл. матем. и матем. физ. 2010. Т. 50. № 8. С. 1520–1531.

Система Orphus

Загрузка...
Вверх