«Математика» 2010 4

Вычислительная оценка сложности полиномиальных представлений булевых функций

Авторы: А. С. Казимиров, С. Ю. Реймеров
Аннотация:

В статье рассматривается сложность полиномиальных представлений булевых функций. Предложены условия, которым должна удовлетворять функция, имеющая сложность больше заданной. С помощью генетического алгоритма минимизации получены верхние оценки сложности таких булевых функций, и как следствие получена новая верхняя оценка сложности для всех булевых функций.
Ключевые слова: булевы функции, полиномиальные представления, минимизация, генетические алгоритмы
УДК: 519.7
Литература: 1. Винокуров С. Ф. Верхняя оценка сложности булевых функций в классе ПНФ / С. Ф. Винокуров, А. С. Казимиров // Algebra andModel Theory 4. – Novosibirsk: Novosibirsk State Tech. University, 2003. – P. 160–165.
2. Казимиров А. С. Оценка числа классов LP-эквивалентности булевых функций / А. С. Казимиров // Вестн. Бурят. ун-та. Сер. 13, Математика и информатика. – 2005. – Вып. 2. – С. 17–22.
3. Казимиров А. С. Параллельные генетические алгоритмы в задачах минимизации булевых функций / А. С. Казимиров // Вестн. ТГУ. Приложение. – 2006. – № 17. – С. 226–230.
4. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К. Д. Кириченко // Дискретная математика. – 2005. – Т. 17, № 3. – С. 80–88.
5. Реймеров С. Ю. О сложности полиномиальных представлений булевых функций 7 переменных / С. Ю. Реймеров // Студент и научно-технический прогресс: Математика : материалы XLVIII междунар. науч. студ. конф. – Новосибирск : Новосиб. гос. ун-т, 2010. – С. 177.
6. Рябец Л. В. Нахождение минимальных полиномов булевых функций с использованием специальной операторной формы / Л. В. Рябец // Технологии Microsoft в теории и практике программирования : тез. докл. – Новосибирск, 2006. – С. 215–217.
7. Even S. On minimal modulo 2 sums of products for switching functions / Even S // IEEE Trans. Electron. Comput. – 1967. – Vol. EC-16, N 10. – P. 671–674.
8. Gaidukov A. Algorithm to derive minimum ESOPs for 6-variable functions / A. Gaidukov // Proceedings of the 5th International Workshop on Boolean Problems 2002. Freiberg, Germany, Sept. 19-20. – 2002. – P. 141–148.