List of issues > Series «Mathematics». 2010. Vol. 4
Computational bound on complexity of polynomial represen- tations of boolean functions
This paper concerns complexity of exclusive-or-sum-of-products expressions representing Boolean functions. Conditions for functions having complexity over a given number are introduced. Genetic minimization algorithm gave obtained upper bounds on complexity of such functions. As a result a new upper bound on complexity for all Boolean functions is obtained.
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.