Том 7, серия 1, номер 2, 2000 г., Стр. 86-95
УДК 519.714
Д. Ю. Черухин
Сверхквадратичные нижние оценки сложности формул в некоторых базисах
Аннотация:
Исследуется сложность булевых формул в полных базисах. В некоторых базисах получены нижние оценки сложности вида$n^{2+c}$ ,$c>0$ , для последовательности функций Андреева.
Библиогр. 11.
Черухин Д. Ю. 1
1. МГУ, мех.-мат. факультет,
Воробьевы горы, 119899 Москва, Россия
е-mail: dyucher@mech.math.msu.su
Статья поступила 20 марта 2000 г.
