Черухин Д. Ю. Нижние оценки сложности булевых функций. - М.: График Без Границ, 2005. - 72 с.
Брошюра является введением в круг задач, относящихся к нижним оценкам сложности булевых функций. В ней доказаны нелинейные нижние оценки сложности в классических моделях вычислений: формулах, контактных схемах, монотонных схемах из функциональных элементов. За основу был взят материал, который автор обычно рассказывает на просеминаре по дискретной математике для студентов младших курсов мехмата МГУ. Для замкнутости изложения добавлены вводные сведения о булевых функциях и некоторые факты из асимптотической теории сложности. В конце каждого параграфа есть упражнения для самостоятельной работы. Изложение опирается на элементарную математику. Для понимания достаточно знаний в рамках школьной программы.
Для студентов младших курсов и старшеклассников, интересующихся дискретной математикой.
На обложке использован рисунок художника Александра Шумилина.