Введение
1 Предварительные сведения 24
2 Верхняя оценка функции Шеннона в базисе
3 Нижняя оценка для почти всех булевых функций в базиcе
3.1 Результаты главы 3 32
3.2 Вспомогательные сведения 33
3.3 Доказательство нижней оценки 40
4 Сложность симметрических функций в базисе
4.1 Результаты главы 4 44
4.2 Доказательство теоремы 4.1 45
4.3 Доказательство теоремы 4.2 61
5 Оценки функции Шеннона в базисах
5.1 Результаты главы 5 62
5.2 Вспомогательные сведения 63
5.3 Доказательство теоремы 5.2 68
5.4 Доказательство теоремы 5.3 73
5.5 Доказательство теоремы 5.5 90
Заключение 95
Список литературы 97
