Содержание к диссертации
Введение
1 Нижние оценки 21
Дополнительные определения и обозначения 21
Типы операций и элементов 21
Метод элиминации элементов 22
Упрощение схемы при подстановках 24
Меры сложности схем 25
1.1 Нижняя оценка 7n/3 - O(1) для функций высокой степени 27
1.1.1 Мультипликативная сложность и полиномы над F2 27
1.1.2 Доказательство нижней оценки 28
1.2 Нижняя оценка 3n - o(n) для аффинных дисперсеров сублинейной размерности 32
1.2.1 Аффинные дисперсеры 32
1.2.2 Доказательство нижней оценки 33
1.3 Нижняя оценка (3 + 816)n - o(n) для аффинных дисперсеров сублинейной размерности 36
1.3.1 Схемы с циклами 36
1.3.2 Преобразования циклических схем 40
1.3.3 Однопроходные квадратичные источники глубины два 49
1.3.4 Мера сложности 52
1.3.5 Доказательство нижней оценки 57
1.3.6 Полное доказательство 61
1.4 Нижняя оценка 3.11n для квадратичных дисперсеров субли нейной размерности 77
1.4.1 Квадратичные дисперсеры 77
1.4.2 Доказательство нижней оценки 80
1.5 Нижняя оценка 5n - o(n) в базисе U2 для линейных функций 88
1.5.1 Линейные функции 88
1.5.2 Доказательство нижней оценки 89
1.6 Нижняя оценка 3.24n на схемную сложность в среднем в базисе U2 для дисперсера относительно проекций 95
1.6.1 Предварительные определения и леммы 97
1.6.2 Основная теорема 104
1.6.3 Нижняя оценка на схемную сложность в среднем 107
1.7 Ограничения метода элиминации элементов 114
2 Верхние оценки 117
2.1 Автоматическое нахождение эффективных схем 117
2.1.1 Сведение 118
2.1.2 Верхняя оценка для MOD3n 120
2.2 Верхняя оценка для вычисления всех MOD-функций одновременно 125
2.2.1 Кодировки 126
2.2.2 Вспомогательные блоки 127
2.2.3 Доказательство оценки 131
Заключение 133
Литература 133
- Метод элиминации элементов
- Однопроходные квадратичные источники глубины два
- Нижняя оценка 3.24n на схемную сложность в среднем в базисе U2 для дисперсера относительно проекций
- Верхняя оценка для вычисления всех MOD-функций одновременно
Метод элиминации элементов
Как было продемонстрировано в предыдущих разделах, критическим случаем в доказательствах нижних оценок, основанных на методе элиминации элементов, является ситуация, когда рассматриваемая переменная входит в два 0-элемента. В такой ситуации мы не можем подставить константу данной переменной так, чтобы сделать один из этих элементов константой. Чтобы найти хорошую подстановку и в таком проблемном случае, мы будем использовать линейные подстановки в данном разделе. Для этого, в свою очередь, нам понадобится функция, устойчивая относительно таких подстановок.
Определение 19 (аффинный дисперсер). Функция f Є Вп называется аффинным дисперсером размерности d, если она не обращается в константу ни на каком аффинном подпространстве F размерности хотя бы d.
Понятие дисперсера является обобщением понятия экстрактора — функции, которая получает на вход последовательность битов в соответствии с некоторым распределением и выдаёт бит, распределение которого статистически близко к равномерному. В отличие от экстракторов, дисперсерам требуется выдавать просто неконстантный бит. Чтобы задать распределение, обычно задают класс источников J7, где каждое X Є Т — это распределение на F . Поскольку дисперсеры выдают просто неконстантный бит, мы отождествляем X с его носителем на F . Функция / Є Вп называется дисперсером для класса источников J7, если /(Х) = 2 для любого X Є Т. Поскольку существуют источники (даже с почти полной энтропией), из которых невозможно извлечь даже один неконстантный бит, изучаются различные частные случаи источников: см. обзор Р. Шалтиела [51]. В данной работе мы будем использовать аффинные источники и их обобщение — источники для полиномиальных многообразий. Аффинные дисперсеры изучаются очень активно в последнее время. В частности, были построены явные конструкции аффинных дисперсеров для размерности d = о(п): [5, 61, 36, 51, 4]. Дисперсеры для полиномиальных многообразий в полях большого размера изучались в З. Двиром [17], дисперсеры для F2 изучались Г. Коэном и А. Талем [11].
В данном разделе доказывается следующая нижняя оценка. Теорема 20 ([13]). Пусть f Є Вп — аффинный дисперсер размерности d. Тогда для любой схемы С, вычисляющей f, верно gates (С) Зп — Ш. В частности, число элементов в схеме, вычисляющей аффинный дисперсер сублинейной размерности, не меньше Зп — о{п). Для доказательства нижней оценки будет удобно использовать так называемые XOR-схемы. Определение 21 (XOR-схема). XOR-схемой называется схема над базисом В і, в которой в качестве входов разрешено использовать не только переменные, но и произвольные линейные функции от входных переменных. Рассмотрим следующую меру сложности XOR-схемы С: /i(C) = gates(C) + inputs (С), где, как обычно, gates и inputs обозначают, соответственно, число внутренних и входных элементов. Нетрудно видеть, что если минимальный элемент XOR-схемы С имеет тип 0, то его можно заменить на входной элемент (новый или старый). При этом мера /І не увеличится. яГ у (B z ) (у) (z) IS) (Л) Теорема 20 является непосредственным следствием следующей леммы (при D = Щ). Лемма 22. Пусть f Є Вп — афинный дисперсер размерности d, S С F2 — аффинное подпространство F размерности D, а С — схема, вычисляющая f на S (то есть для любого х Є S, С(х) = f(x)). Тогда /І(С) 4 (Г) — d — 1).
Доказательство. Доказательство проведём индукцией по D. База D d+ 1 выполнена. Для перехода рассмотрим схему С с минимальным значением /І. Пусть А — минимальный элемент, входами которого являются линейные функции х и у (такой элемент точно есть, поскольку / на S не может считать линейную функцию, так как D d + 1). Если А имеет тип 0, то его можно заменить на вход (не увеличив при этом /І), поэтому допустим, что А вычисляет произведение, то есть (х 0 Сі)(у 0 CQ) 0 С, где Сі,С2,С Є F2. Мы сделаем подстановку х (— сі или у — c i. (Делать такие подстановки будем точно так же, как и для обычных схем: удалим все элементы, хотя бы один из входных проводов которых начал вычислять константную функцию.) Это даёт аффинное подпространство F размерности хотя бы D — 1 (если бы размерность упала до нуля, это означало бы, что х или у вычисляют константу на S, что противоречило бы оптимальности схемы). Ниже мы покажем, что при подстановке /І уменьшится хотя бы на 4. Для этого мы рассмотрим два случая.
Случай 1. Исходящая степень х и у равна 1 (а исходящая степень у может быть 1 или больше). Подставим х (— с\. Это тривиализирует А до с, поэтому всего его потомки тоже удаляются. У А обязан быть хотя бы один потомок, поскольку если бы А оказался выходным элементом, то вся схема стала бы константой на аффинном подпространстве размерности хотя бы d. Таким образом, при подстановке удаляются два элемента, а также пропадает зависимость от двух входов (х и у), поэтому /І уменьшается хотя бы на 4.
Случай 2. Исходящая степень, скажем, х хотя бы два. (х) Су) -Е 0 А{Л) СО
Пусть В — другой потомок х и пусть С потомок А. Подставим х (— с\. Это удалит вход х и элементы Л, В и С. Если В = С, то С также становится константой (поскольку оба его входа вычисляют константы после подстановки), поэтому удалятся и его потомки. Таким образом, в этом случае удаляется хотя бы один вход и хотя бы три элемента, поэтому /І снова уменьшается хотя бы на 4.
На сегодняшний день это самая сильная известная нижняя оценка на схемную сложность функции из NP. Её доказательство также является наиболее технически трудным в данной работе.
В данном разделе нам понадобится другое обобщение схем. Это необходимо для того, чтобы оставаться в нужном классе схем в процессе элиминации элементов.
Определение 24 (схема с циклами). Схемой с циклами называется ориентированный граф, необязательно являющийся ациклическим, в котором все вершины имеют входящую степень 0 или 2. Размер схемы, входные и внутренние элементы определяются так же, как и для обычных схем. Аффинной схемой с циклами называется схема с циклами, в которой каждый элемент вычисляет аффинную операцию. Как правило, все элементы такой схемы вычисляют операции 0 и =, но по техническим причинам мы допускаем также проходные и тривиальные элементы. Мы будем рассматривать схемы с несколькими выходами, поэтому, в отличие от обычных схем, вычисляющих булевы предикаты, у аффинной схемы с циклами в качестве выходных может быть помечено несколько элементов и они не обязаны иметь исходящую степень, равную нулю.
Аффинная схема с циклами соответствует системе уравнений над F2. Переменные этой системы — значения элементов. Операция внутреннего элемента задаёт уравнение на входные и выходное значение элемента. Входные элементы учитываются в столбце свободных членов (поскольку нас будут интересовать решения системы уравнений в ситуации, когда входным элементам присвоены константные значения). Таким образом, мы имеем отдельную систему уравнений для каждого набора значений входных элементов, но у всех этих систем общая матрица. Если в элемент G ведут провода из F и Н и этот элемент вычисляет операцию 0, мы записываем уравнение G 0 (F 0 Н) = 0. Например, если G вычисляет F 0 х 0 1, где х — входной элемент, тогда соответствующим уравнением будет GF = ж 01; в данном случае элементы G и F соответствуют двум единицам в матрице, а х 0 1 — это правая часть уравнения. Для аффинной схемы с циклами соответствующая система уравнений имеет квадратную матрицу.
Однопроходные квадратичные источники глубины два
Начиная со следующего случая мы будем рассматривать топологически первый Л-элемент А, то есть такой /\-элемент, который не достижим ни из какого другого А-элемента. Он существует, потому что циклы возможны только в линейной части схемы.
Отметим, что схема С обязана содержать хотя бы один Л-элемент (иначе она считала бы аффинную функцию и её можно было бы превратить в константу одной линейной подстановкой). Минимальность А означает, что оба входа А вычисляются честными аффинными полусхемами (заметим, что подсхема честной схемы является честной, поскольку соответствует подматрице матрицы полного ранга); в частности, они могут быть входами.
Заметим, что х незащищена по случаю 1 и ж не может входить в Q по правилу 4. Подставив в х константу, тривиализирующую А, удалим двух потомков ж, всех потомков А и сделаем Q О-элементом, который удалится правилом 1. Это даст подстановку типа 3. (Как обычно, если единственный потомок А совпадает с другим потомком ж, тогда этот элемент становится константой и удаляются ещё и его потомки. Значит, в любом случае удаляются хотя бы четыре элемента.) Случай 7. Один из входов А — внутренний элемент Q. Обозначим другой вход через Р. Если Р — тоже внутренний элемент и его исходящая степень больше Q, поменяем Р и Q ролями.
Мы подставим в Q константу, тривиализирующую А. Элемент Q вычисляется аффинной честной схемой, значит, вычисляет функцию с 0 ЄВІЄІХІ. Заметим, что / ф 0 по правилу 2. Для этого мы будем использовать перестроение из леммы 32. Чтобы выполнить его, нам понадобится хотя бы одна незащищённая переменная ХІ, где і Є I.
Случай 7.1. Такая переменная х\ есть.
Добавим подстановку х\ = Ъ 0 с 0 ф дт ХІ в ОК-источник R для подходящей константы Ъ (так что Q на R вычисляет константу, тривиализирующую А). Мы хотели бы просто заменить операцию, вычисляющуюся в Q, на эту константу. Однако нам нужно удалить только что подставленную переменную Х\ из схемы. Для этого мы используем перестройку из леммы 32. Заметим, что она изменяет входящие и исходящие степени только у х\ (заменяя его на Z) и Q. Новые специальные элементы при этом не появляются, и последующее применение правила 2 к Q удаляет Q тоже без введения новых специальных элементов.
Более того, нормализация удаляет всех потомков Q, всех потомков А и, в случае outdeg(P) = 1, правило 1 удаляет Р, если он является внутренним элементом, или Р становится 0-переменной, если он был переменной. Остаётся оценить, насколько уменьшилась мера.
Ниже мы проводим такую оценку, рассмотрев несколько случаев в зависимости от типа Р. Случай 7.1.1. Q является 2+-элементом. Напомним, как происходит перестройка. (X\\ PQ ()Q АЛІ перестройка После перестройки удалятся хотя бы три потомка Q и хотя бы один потомок А, что даёт подстановку типа 3. Случай 7.1.2. Q является внутренним 1-элементом, Р — входным. Тогда Р — 1-переменная и не защищена (см. случаи 6, 1). \1 [Р) (0)Q Ж/\) перестройка @XDQ АЛ) Отметим, что Р ф жі, поскольку единственное исходящее из Р ребро идёт в Л-элемент. Это означает, что Р не затрагивается перестройкой. После тривиализации А схема становится независимой от х\ и Р, что даёт подстановку типа 2.
Случай 7.1.3. Q — внутренний 1-элемент, а Р — внутренний. Тогда исходящая степень Р равна одному (если бы она была больше, мы поменяли бы Р и Q ролями). р(0) Г) 5 А\л) перестройка P@XDQ AU\)
Опять же, P не затрагивается перестройкой, поскольку у него всего один потомок и он типа , в то время как перестройка затрагивает линейную часть схемы. После подстановки удаляются два потомка Q, хотя бы один потомок A, а P становится 0-элементом. Это даёт подстановку типа 3. Заметим, что P не может быть потомков Q по правилу 4. Случай 7.2. Все переменные из аффинной функции, вычисляемой в Q, защищены.
Случай 7.2.1. Оба входа Q — скажем, Xj и Xk — являются переменными, входящими в правую часть одного и того же квадратичного урванения w = (XJ 0 c)(xk 0 с ) 0 с". Сделаем подстановку Xj = Xk 0 d" (используя утверждение 28), чтобы тривиализиро-вать А. Это удалит квадратичную подстановку (и не затронет другие квадратичные подстановки, потому что Xj и Xk в них не входят), Q, А, их потомка (и даже больше, но это уже неважно), что даёт А/І 3/3 + aQ + а/, то есть подстановку типа 7.
Случай 7.2.2. Q является 2+-элементом. Возьмём j Є /. Пусть Xj входит в квадратичную подстановку хр = (XJ 0 a)(xk 0 b) 0 с. Напомним, что к этому моменту все защищённые переменные являются 1-переменными, входящими в 0-элементы (см. случаи 1 и 2). Подставим в Xk константу d и нормализуем схему. Это удалит последователя Xk, квадаратичную подстановку и сделает Xj незащищённой. Если при этом удалится хотя бы два элемента, то А/І 2/3 + aQ + а/, подстановка типа 7. В дальнейшем мы предполагаем, что после подстановки Xk — d удаляется только потомок Xk.
Если элемент Q не зависит от Xk, тогда его исходящая степень будет хотя бы 2 после подстановки Xk — d и нормализации. Если в Q идёт провод из Xk, тогда его второй вход должен быть внутренним 0-элементом Q (если бы это был входной элемент, это была бы переменная Xj, но тогда мы бы оказались в случае 7.2.1). Тогда после подстановки Xk — d и нормализации Q элемент Q входит в А и имеет исходящую степень хотя бы 2. Обозначим Q через Q в этом случае.
Нижняя оценка 3.24n на схемную сложность в среднем в базисе U2 для дисперсера относительно проекций
Если t к, то правая часть неравенства не больше нуля, поэтому предположим, что t к. Допустим, что схема С оптимальна относительно меры /І (то есть С имеет минимальное значение /І среди всех схем, вычисляющих / на S). Мы найдём элемент G в схеме С, вычисляющий функцию д степени не более 2 и рассмотрим два (n, t + 1)-квадратичных многообразия S: So = {х Є S: д(х) = 0} и So = {х Є S: д(х) = 1}. Пусть 5о = Po\S\ и \Si\ = pi\S\, где 0 po,Pi 1 и po+Pi = 1 (заметим, что pi = 0 или Pi = 1 означало бы, что G вычисляет константу на S, что противоречило бы тому, что С оптимальна). Устранив из С все элементы, которые не зависят от хотя бы от одного из своих входов на Si, получим схему С , вычисляющую / на Si. Допустим, что /І(С) —/І(С ) Aj. Тогда по предположению индукции м(С) /i(Cj) + Aj min {/3(log2 I S — log2 s — 1), 2(& — ( + 1))} + Aj Г / 1 \ A l = min p (log2 о — log2 s — 1) + Aj — p log2 — , 2(k — t) + (Aj — 2) . Pi Следовательно, если A,- /31og9 — и A,- 2 при і = 0 или і = 1, то требуемое неравенство следует по предположению индукции. Неравенство А Aj (3 \0g2l/Pi верно, если pi 2 г. Поскольку мы хотим, чтобы это неравенство выполнялось хотя бы для одного изі = 0иі = 1и поскольку Ро + Pi = 1, заключаем, что достаточно, чтобы выполнялось такое неравенство: AQ Д-L 2 + 2 1 и Ао, Ai 2 . (1.9) Рассмотрев несколько случаев, мы покажем, что всегда найдётся элемент G, для которого соответствующие Ао и Ai удовлетворяют неравенству (1.9). Для этого мы будем использовать неравенства (1.3)–(1.8).
Для начала покажем, что схема С обязана быть непустой (напомним, что С является XOR-схемой, что означает, что её входами являются не только переменные, но и произвольные аффинные комбинации переменных). Действи тельно, если С пуста, то она вычисляет линейную функцию /. Следовательно / — константа и на So = {х Є S: 1{х) = 0}, и на Si = {х Є S: 1{х) = 1}. Однако max{5o, Si} $/2 s, что противоречит тому факту, что / является (п, к, й)-квадратичным дисперсером.
Пусть А — Л-элемент с максимальным числом Л-элементов от него до выхода схемы С. Другими словами, для фиксированного Л-элемента мы рассматриваем все ориентированные пути от этого элемента до выхода и выбираем среди таких путей тот, на котором больше всего Л-элементов; после этого мы выбираем Л-элемент, для которого этот показатель максимален. Поскольку С — XOR-схема, можно считать, что А — минимальный элемент, то есть его непосредственными предками являются входные элементы. Обозначим эти входные элементы через х и у. Случай 1. oiitdeg(rr) = outdeg(y) = 1. Случай 1.1. outdeg(A) = 1 и из А идёт провод в Л-элемент В. Пусть С — второй вход В (он может быть входным или внутренним элементом). Случай 1.1.1. outdeg(C) = 1. Б (Л)
Тривиализируем А соответствующей квадратичной подстановкой. Тогда элемент В удалится. Более тога, А = 0 или А = 1 тривиали-зирует также Б, поэтому все его потомки, а также элемент С тоже удаляются (поскольку С используется только для вычисления Б, а В стал константой). В обоих случаях х и у также элиминируются (единственный элемент Л, в который шли провода из этих входов, теперь вычисляет константу). Получаем {До, Ді} = {2+2а, З+За} (здесь и далее при удалении элемента, про который неизвест но, входной он или внутренний, мы будем считать, что он даёт вклад хотя бы а в уменьшение меры; так можно делать, поскольку а 1). Необходимые неравенства (1.9) следуют из (1.5).
По выбору А, элемент С вычисляет функцию степени не выше 2. Сделаем С константой. В обоих случаях мы удаляем потомков С и сам элемент С. Это уменьшает меру хотя бы на 2 + а. В одном из случаев В также становится константой, что удаляет , Д и входы х и у. Получаем {До, Ді} = {2 + а, 4 + За}. Данные До, Ді удовлетворяют неравенствам (1.9) по (1.3). Случай 1.2. outdeg(A) = 1 и из А идёт провод в 0-элемент В. По выбору А второй вход В вычисляет функцию степени не выше 2. Поэтому сам В вычисляет функцию степени не более 2. Сделаем В константой. Это удаляет В и его потомков. Элемент А и входы х и у также удаляются. Следовательно, До = Ді = 3 + 2а. Неравенства (1.9) выполняются по (1.8).
Верхняя оценка для вычисления всех MOD-функций одновременно
Необходимая верхняя оценка следует непосредственно из существования такого блока. Чтобы получить схему размера Зп + 0(1), мы соединяем в це почку п/3 копий блока размера девять. Каждый следующий блок прибавляет к текущему остатку по модулю три сумму трёх новых битов. В самом конце получаем остаток по модулю три суммы всех входных п битов, и остаётся просто проверить, равен ли он г.
Как уже упоминалось ранее, нелинейных нижних оценок на данный момент мы не знаем не только для функций из Вп (то есть булевых предикатов), но и функций из Вщп (булевых функций с п входами и п выходами). Подсчётом можно показать, что схемная сложность п симметрических функций от п переменных есть Q(n2 (l ) почти для всех наборов из п симметрических функций. Есть три естественных подкласса симметрических функций: ЕХП Є Вп равна 1 тогда и только тогда, когда сумма входных п битов равна к; THRn Є Вп равна 1 тогда и только тогда, когда сумма входных п битов хотя бы к; MOD 7 Є Вп равна 1 тогда и только тогда, когда сумма входных п битов сравнима с г по модулю ш;
Известно (см. следствие 72 далее), что наборы функций {EX, EXІ,..., EX} и {TH, THІ,..., TH} . можно посчитать схемами линейного размера. В данном разделе мы покажем, что все MOD-функции для 1 т п также можно посчитать схемами малого (но всё же нелинейного) размера. Для п целых чисел Гі,Г2,... ,гп через ALLMODJ .1 " 7 " обозначим набор {MODi ri, MODjra,..., MOD "} Если г\ = Т 2 = гп = г, будем писать просто ALLMODJ .. Основным результатом данного раздела является следующая оценка. Теорема 68 ([15]). gates(ALLMOD ) = 0{п). В работе [15] также доказывается, что gates(ALLMOD 1 " 7) = 0{п log log n).
Перед доказательством основного результата мы приводим некоторые вспомогательные факты. В большинстве оценок мы опускаем целые части (то есть пишем, например, log2n вместо log2n]). Это не влияет на асимпто v n тическое поведение оцениваемых величин. Через л мы обозначаем І=ІХІ. Мы также будем опускать п, когда оно ясно из контекста. Через log ж и In ж будем обозначать логарифм х по основаниям 2 и е, соответственно. Лемма 69. 1. Гармонический ряд ([3], теорема 2.5.3): Е 1 — = Inn + 0(1). к 1 к п 2. Гармонический ряд простых ([3], теорема 8.8.5): А/1 Рп = - = In Inn + O(l). р р п,рє 3. Асимптотический закон распределения простых чисел ([3], теорема 8.8.1): число простых чисел, не превосходящих n, есть П 7г(п) = G 2.2.1 Кодировки Для заданного m N есть два естественных способа кодировать остаток r по модулю m бинарными строками: 126 bin(r,m) = (бо, &ъ , &iogm) logm-битовое двоичное представление г: У Ь,{1% = г . 0 i logm еж (г, ш) = (ео, Єї,..., ето_і) — m-битовая строка, такая что ег = 1 и е = О для всех 0 к т — 1, к Ф г.
Конечно же, первое представление более компактно. Второе представление, однако, позволяет очень просто проверить, задаёт ли данная битовая строка конкретный остаток (достаточно прочитать соответствующий бит). Например, чтобы проверить, задаёт ли данная строка & G Fj остаток б mod 10, нужно вычислить бит (&o) Л Ъ\ Л &2 Л ( з), в то время как чтобы проверить, задаёт ли данная 10-битовая строка е тот же остаток, достаточно прочесть бит е%.
Следующие две леммы хорошо известны и могут быть найдены, например, в [55, раздел 3.4]. Их доказательства сравнительно просты, и мы приводим их основные идеи для полноты изложения.
Лемма 70. Существует схема размера 0{п), принимающая на вход п битов xi,..., хп и выдающая Ып(Х,п + 1), то есть двоичное представление X.
Доказательство. Необходимая схема строится из блоков под названием Full Adder (FA). Такой блок вычисляет функцию из з,2, которая на входе (x,y,z) выдаёт два бита (carry, sum), таких что х + у + z = 2 carry + sum (то есть младший и старший бит суммы). Этот блок можно реализовать пятью элементами.