Том 21, номер 5, 2014 г., Стр. 76-94

УДК 519.714.7
Чухров И. П.
Минимальные комплексы граней случайной булевой функции

Аннотация:
Для почти всех булевых функций $n$ переменных доказано, что число минимальных относительно меры сложности комплексов граней не превосходит $2^{2^{n-1}\left(1+o\left(1\right)\right)}$, если максимальная длина минимальных и длина кратчайших комплексов граней асимптотически равны. Для аддитивных мер сложности получены эффективно проверяемые достаточные условия, при которых асимптотически равны максимальная длина минимальных и длина кратчайших комплексов граней для почти всех булевых функций.
Библиогр. 17.

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

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

Статья поступила 19 декабря 2013 г.

Литература

[1] Андреев А. Е. Об одной модификации градиентного алгоритма // Вестн. МГУ. Математика. Механика. - 1985. - №3. - С. 29–35.

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

[3] Глаголев В. В. Некоторые оценки ДНФ булевых функций алгебры логики // Пробл. кибернетики. - 1967. - № 19. - С. 75–94.

[4] Журавлёв Ю. И. Оценка для числа тупиковых д.н.ф. функций алгебры логики // Сиб. мат. журн. - 1962. - Т. 3, №5. - С. 802–804.

[5] Журавлёв Ю. И. Алгоритмы построения минимальных ДНФ // Дискретная математика и математические вопросы кибернетики. Т. 1. - М.: Наука, 1974. - С. 67–98.

[6] Коршунов А. Д. Сравнение сложности длиннейших и кратчайших ДНФ и нижняя оценка числа тупиковых ДНФ для почти всех булевых функций // Кибернетика. - 1969. - № 4. - С. 1–11.

[7] Коршунов А. Д. О сложности кратчайших дизъюнктивных нормальных форм случайных булевых функций // Методы дискретного анализа в оптимизации управляющих систем. - Новосибирск: Ин-т математики СО АН СССР, 1983. - №40. - С. 25–53.

[8] Кузнецов С. Е. О нижней оценке длины кратчайшей ДНФ почти всех булевых функций // Вероятностные методы и кибернетика. - Казань: Изд-во Казан. ун-та, 1983. - № 19. - С. 44–47.

[9] Лин Син-Лян О сравнении сложностей минимальных и кратчайших дизъюнктивных нормальных форм для функций алгебры логики // Пробл. кибернетики. - 1967. - №18. - С. 11–44.

[10] Нигматуллин Р. Г. Сложность булевых функций. - М.: Наука, 1991. - 240 с.

[11] Сапоженко А. А. Введение в дискретную математику. - М.: Изд-во МГУ, 1975. - 90 с.

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

[13] Чухров И. П. О ядровых и кратчайших комплексах граней в единичном кубе // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 2. - С. 75–94.

[14] Чухров И. П. О минимальных комплексах граней в единичном кубе // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 3. - С. 79–99.

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

[16] Яблонский С. В. Введение в дискретную математику. - М.: Высш. шк., 2003. - 384 с.

[17] Pippenger N. The shortest disjunctive normal form of a random Boolean function // Random Struct. Algorithms. - 2003. - Vol. 22, N2. - P. 161–186.