Том 25, номер 3, 2018 г., Стр. 126-151

УДК 519.714.7
Чухров И. П.
О сложности минимизации квазициклических булевых функций

Аннотация:
Исследуются булевы функции, которые сочетают экстремальные значения характеристик сложности минимизации, неприменимость локальных методов сокращения трудоёмкости перебора и невозможность эффективного использования достаточных условий минимальности. Построены квазициклические функции, которые обладают свойствами циклических и поясковых функций, доминирования множеств вершин, выполнимостью достаточных условий минимальности, основанных на независимых семействах множеств. Для таких функций получены экспоненциальные нижние оценки протяжённости и специальных множеств, а также дважды экспоненциальная нижняя оценка числа кратчайших и минимальных комплексов граней с различными множествами собственных вершин.
Библиогр. 13.

Ключевые слова: минимизация булевых функций, сложность, протяжённость, доминирование, семейство независимых множеств.

DOI: 10.17377/daio.2018.25.601

Чухров Игорь Петрович ¹
1. Институт автоматизации проектирования РАН,
ул. 2-я Брестская, 19/18, 123056 Москва, Россия
е-mail: chip@icad.org.ru

Статья поступила 24 ноября 2017 г.
Исправленный вариант — 19 января 2018 г.

Литература

[1] Васильев Ю. Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. Т. 1. М.: Наука, 1974. С. 99–148.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 c.

[3] Евдокимов А. А. О максимальной длине цепи в единичном $n$-мерном кубе // Мат. заметки. 1969. Т. 6, № 3. С. 309–319.

[4] Журавлёв Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // Дискретная математика и математические вопросы кибернетики. Т. 1. М.: Наука, 1974. С. 67–98.

[5] Кудрявцев В. Б., Андреев А. Е. О сложности алгоритмов // Фунд. прикл. математика. 2009. Т. 15, № 3. С. 135–169.

[6] Максимов Ю. В. Реализация булевых функций с ограниченным числом нулей в классе дизъюнктивных нормальных форм // Журн. вычисл. математики и мат. физики. 2013. Т. 53, № 9. С. 1569–1588.

[7] Панов А. В. Алгоритмы, использующие окрестности первого порядка для минимизации булевых функций // Журн. вычисл. математики и мат. физики. 2013. Т. 53, № 9. С. 1589–1600.

[8] Сапоженко А. А, Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм // Итоги науки и техники. Сер. Теория вероятностей. Мат. статистика. Теор. кибернетика. 1987. Т. 25. С. 68–116.

[9] Чухров И. П. Оценки числа минимальных дизъюнктивных нормальных форм для поясковой функции // Методы дискретного анализа в исследованиях функциональных систем. Новосибирск: Ин-т математики СО АН СССР, 1981. № 36. С. 74–92.

[10] Чухров И. П. О мерах сложности комплексов граней в единичном кубе // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 6. С. 77–94.

[11] Чухров И. П. О доказательстве минимальности покрытий через обобщение понятия независимости // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 2. С. 87–106.

[12] Coudert O., Sasao T. Two-level logic minimization // Logic synthesis and verification. Norwell, MA: Kluwer Acad. Publ., 2001. P. 1–27. (Springer Int. Ser. Eng. Comput. Sci.; Vol. 654).

[13] Umans C., Villa T., Sangiovanni-Vincentelli A. L. Complexity of two-level logic minimization // IEEE Trans. CAD Integrated Circuits Systems. 2006. Vol. 25, No. 7. P. 1230–1246.