Верхние и нижние оценки на схемную сложность явно заданных булевых функций

• Автор: Деменков, Евгений Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Санкт-Петербург
• Количество страниц: 60 с. : ил.

Оглавление
Введение

1 Определения и результаты

1.1 Схемная сложность

1.2 Методы доказательств оценок на схемную сложность,

использующиеся в работе

1.2.1 Метод элиминации элементов

1.2.2 Метод подсчета элементов

1.2.3 Метод предкодирования

1.3 Результаты

1.3.1 Известные результаты в схемной сложности

1.3.2 Полученные результаты
2 Верхние оценки
2.1 Верхняя оценка 4.5та на функцию, вычисляющую сумму входных битов
2.2 Верхняя оценка на АЬЬМОВ

3 Нижние оценки
3.1 Нижняя оценка Зп — о(п) для аффинного дисперсера .
3.2 Нижняя оценка на вектор из п функций в базисе Щ . .
Литература

Введение
Теория сложности
Теория сложности вычислений изучает зависимость потраченных ресурсов на вычисление некой функции от размера входных данных. В разных моделях вычислений рассматриваются разные виды ресурсов. К примеру, при изучении алгоритмов используют модели, в основе которых лежит машина Тыоринга, а в качестве ресурсов рассматривают обычно время или память, необходимые для вычисления функции. В коммуникационной сложности в качестве ресурса, как правило, выступает суммарный размер переданных сообщений.
Теория сложности интересна как с практической, так и с теоретической точек зрения. Практическая часть включает в себя построение явных конструкций (алгоритмов, протоколов, методов). Теоретическая часть изучает вопрос размера этих конструкций и включает в себя, в частности, доказательство нижних оценок на сложность конструкций.

каждого слагаемого с левой стороны нам известно (это Ь*, умноженное на бинарное представление 2і (mod m)). Сложим все эти числа по модулю тп и получим Ып(г, тп). На каждое такое сложение нужно clogm элементов. Всего нужно сделать logn сложений. □
Тогда для всех простых чисел бинарное представление считается не более чем за
clognlogp< clognlogn =
p = С7г(: — ) log2 П = 0( n/l0gn log2 n = O(n)3 log n log (n/ logn) J
Заметим, что число чисел, представим в виде А;—ой степени простого числа и меныни п, меньше tfn. Тогда для степеней простых чисел:
УУ с logn log;/ < J] с logn log п <
рк<п/ 1пп,р£Р,к>1 рк<п/ In п,реР,к>
< (/п + /п + .. ,)clog2 п = о(п).

Теперь построим блок Б4.
Лемма 2.2.3. Существует схема линейного размера, которая вычисляет ех{х + ... + хп, т) для всех т < у/п.
Зтг(п) — это количество простых чисел, меньших п. Согласно закону распределения простых чисел, тг(п) = 0(п/ logn).