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

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

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

Заявление

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

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

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

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

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

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

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

Границы на AC0схемы

Лемма переключения является ключевым инструментом, используемым для понимания класса сложности схемы AC 0 , который состоит из схем постоянной глубины, состоящих из AND, OR и NOT. Первоначальное применение этой леммы Хостадом состояло в установлении точных экспоненциальных нижних границ для таких схем, вычисляющих PARITY , улучшая предыдущие суперполиномиальные нижние границы Меррика Фурста, Джеймса Сакса и Майкла Сипсера ^[3] и независимо Миклоша Айтая . ^[4] Это делается путем применения леммы переключения раз , где — глубина схемы: каждое применение удаляет слой схемы, пока не останется очень простая схема, тогда как PARITY все еще остается PARITY при случайном ограничении и, таким образом, остается сложной. Таким образом, схема, вычисляющая PARITY, должна иметь высокую глубину. ^[5] ${\displaystyle d-1}$ ${\displaystyle d}$

Лемма о переключении является основой для границ спектра Фурье схем AC ^{0 [5]} и алгоритмов обучения таких схем. ^[6]

Смотрите также

• АС 0
• Булева схема
• Выполнимость схемы
• Проблема с оценкой цепи
• Функция четности

Ссылки

1. Хастад, Йохан (1986). "Почти оптимальные нижние границы для схем малой глубины". Труды восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . ACM Press. стр. 6–20. doi :10.1145/12130.12132. ISBN 978-0-89791-193-1.
2. Россман, Бенджамин (2019). «Критичность регулярных формул». Михаэль Вагнер. Schloss Dagstuhl – Центр информатики Лейбница: 28 страниц. doi : 10.4230/LIPICS.CCC.2019.1 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
3. Меррик Ферст, Джеймс Сакс и Майкл Сипсер, «Четность, схемы и иерархия полиномиального времени», Annu. Intl. Symp. Found. Computer Sci., 1981, Теория вычислительных систем , т. 17, № 1, 1984, стр. 13–27, doi :10.1007/BF01744431
4. Миклош Айтай, « Формулы конечных структур», Annals of Pure and Applied Logic , 24 (1983) 1–48. ${\displaystyle \Sigma _{1}^{1}}$
5. Таль, Авишай (2017). «Жесткие границы спектра Фурье AC0». Марк Хербстритт. Schloss Dagstuhl – Центр информатики Лейбница: 31 страница. doi : 10.4230/LIPICS.CCC.2017.15 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
6. Линиал, Натан; Мансур, Ишай; Нисан, Ноам (1993-07-01). «Схемы постоянной глубины, преобразование Фурье и обучаемость». Журнал ACM . 40 (3): 607–620. doi : 10.1145/174130.174138 . ISSN  0004-5411.

• Арора, Санджив ; Барак, Боаз (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