В статье рассматривается сложность полиномиальных представлений булевых функций. Предложены условия, которым должна удовлетворять функция, имеющая сложность больше заданной. С помощью генетического алгоритма минимизации получены верхние оценки сложности таких булевых функций, и как следствие получена новая верхняя оценка сложности для всех булевых функций.

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.