Лемма о переключении

В сложности вычислений теории лемма Хостада о переключениях является ключевым инструментом для доказательства нижних границ размера булевых схем постоянной глубины . Впервые он был введен Йоханом Хостадом, чтобы доказать, что переменный ток ⁰ Булевы схемы глубины k требуют размера $\exp(\Omega (n^{1/(k-1)}))$ вычислить функцию четности на $n$ биты. он был удостоен премии Гёделя Позже в 1994 году за эту работу .

Лемма переключения описывает поведение схемы глубины 2 при случайном ограничении , т. е. при случайном присвоении большинству координат значений 0 или 1. В частности, из леммы следует, что формула в конъюнктивной нормальной форме (т. е. оператор И) ИЛИ) становится формулой в дизъюнктивной нормальной форме (ИЛИ и И) при случайном ограничении, и наоборот. Это «переключение» и дало лемме название.

Заявление

Учитывайте ширину- $w$ формула в дизъюнктивной нормальной форме $F=C_{1}\vee C_{2}\vee \cdots \vee C_{m}$, ИЛИ предложений $C_{\ell }$ которые являются оператором AND для w литералов ( $x_{i}$ или его отрицание $\neg x_{i}$). Например, $(\neg x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})\vee (x_{2}\wedge x_{3})$ является примером формулы в этой форме с шириной 2.

Позволять $F|R_{p}$ обозначим формулу при случайном ограничении: каждый $x_{i}$ устанавливается независимо в 0 или 1 с вероятностью $(1-p)/2$. Тогда для достаточно большой константы C лемма о переключении утверждает, что

$\Pr[\operatorname {DT} (F\mid R_{p})\geq t]<C(pw)^{t},$

где $\operatorname {DT} (f)$ обозначает сложность дерева решений , количество битов $x$ необходимо вычислить функцию $f$.

Доказательство

Интуитивно понятно, что лемма о переключении справедлива, поскольку формулы ДНФ значительно сокращаются при случайном ограничении: когда литералу в предложении присвоено значение 0, все предложение AND оценивается как ноль и, следовательно, может быть отброшено.

Первоначальное доказательство леммы о переключении ( Håstad 1987 ) включает в себя рассуждения с условными вероятностями .Возможно, более простые доказательства были впоследствии даны Разборовым (1993) и Бимом (1994) . Введение см. в главе 14 книги Arora & Barak (2009) .

Границы переменного тока ⁰ схемы

Лемма о переключениях — ключевой инструмент, используемый для понимания схемы класса сложности AC. ⁰ , который состоит из схем постоянной глубины, состоящих из И, ИЛИ и НЕ. Первоначальное применение этой леммы Хостадом заключалось в установлении точных экспоненциальных нижних границ для таких схем, вычисляющих ЧЕТНОСТЬ , улучшая предыдущие суперполиномиальные нижние границы Меррика Ферста , Джеймса Сакса и Майкла Сипсера. и независимо Миклош Айтай . Это делается применением леммы о переключениях $d-1$ времена, где $d$ — это глубина схемы: каждое приложение удаляет слой схемы до тех пор, пока не останется очень простая схема, тогда как ЧЕТНОСТЬ по-прежнему остается ЧЕТНОСТЬю при случайном ограничении и поэтому остается сложной. Итак, схема, вычисляющая ЧЕТНОСТЬ, должна иметь большую глубину.

Лемма о переключении является основой для оценок спектра Фурье AC ⁰ схемы и алгоритмы обучения таких схем.

См. также

• переменного тока ⁰
• Булева схема
• Выполнимость схемы
• Проблема со значением цепи
• Функция четности

Ссылки

• Арора, Санджив ; Барак, Воаз (2009), Сложность вычислений: современный подход , Кембридж , ISBN  978-0-521-42426-4 , Збл   1193,68112
• Бим, Пол (1994), «Букварь к лемме о переключении», рукопись
• Хостад, Йохан (1987), Вычислительные ограничения схем малой глубины (PDF) , доктор философии. диссертация, Массачусетский технологический институт.
• Разборов, Александр А. (1993), «Эквивалентность между арифметикой ограниченной области второго порядка и ограниченной арифметикой первого порядка», Арифметика, теория доказательств и вычислительная сложность , 23 : 247–277, doi : 10.1093/oso/9780198536901.003.0012 , ISBN  978-0-19-853690-1