Том 12, серия 1, номер 2, 2005 г., Стр. 56-72
УДК 519.71
А. В. Чашкин
О сложности реализации булевых функций формулами
Аннотация:
Рассматривается сложность вычисления частичных булевых функций данного веса формулами в базисе$\{\&,\vee,\neg\}$ . Установлено асимптотически точное значение сложности минимальных формул, реализующих почти все$n$ -местные частичные булевы функции данного веса в случае, когда логарифм размера области определения асимптотически равен$n$ . Предложен новый метод реализации монотонных булевых функций формулами.
Чашкин А. В. 1
1. МГУ, мех.-мат. факультет, Воробьевы горы,
119992 Москва, Россия
е-mail: chash@online.ru
Статья поступила 10 декабря 2004 г.
