|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О сложности минимизации квазициклических булевых функций
И. П. Чухров Институт автоматизации проектирования РАН, ул. 2-я Брестская, 19/18, 123056 Москва, Россия
Аннотация:
Исследуются булевы функции, которые сочетают экстремальные значения характеристик сложности минимизации, неприменимость локальных методов сокращения трудоёмкости перебора и невозможность эффективного использования достаточных условий минимальности. Построены квазициклические функции, которые обладают свойствами циклических и поясковых функций, доминирования множеств вершин, выполнимостью достаточных условий минимальности, основанных на независимых семействах множеств. Для таких функций получены экспоненциальные нижние оценки протяжённости и специальных множеств, а также дважды экспоненциальная нижняя оценка числа кратчайших и минимальных комплексов граней с различными множествами собственных вершин. Библиогр. 13.
Ключевые слова:
минимизация булевых функций, сложность, протяжённость, доминирование, семейство независимых множеств.
Статья поступила: 24.11.2017 Переработанный вариант: 19.01.2018
Образец цитирования:
И. П. Чухров, “О сложности минимизации квазициклических булевых функций”, Дискретн. анализ и исслед. опер., 25:3 (2018), 126–151; J. Appl. Industr. Math., 12:3 (2018), 426–441
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da904 https://www.mathnet.ru/rus/da/v25/i3/p126
|
Статистика просмотров: |
Страница аннотации: | 223 | PDF полного текста: | 52 | Список литературы: | 30 | Первая страница: | 1 |
|