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

В теория сложности вычислений, Лемма Хостада о переключениях является ключевым инструментом для доказательства нижней границы размера постоянной глубины Булевы схемы. С помощью леммы о переключениях Йохан Хастад  (1987 ) показало, что Булевы схемы глубины k в котором только И, ИЛИ и НЕ логические ворота разрешены требовать размер

${\displaystyle \exp \left(\Omega \left(n^{\frac {1}{k-1}}\right)\right)}$

для вычисления функция четности.

Лемма о переключении говорит, что схемы глубины 2, в которых некоторая часть переменных была установлена ​​случайным образом, зависят с высокой вероятностью только от очень небольшого числа переменных после ограничения. Название леммы о переключениях происходит от следующего наблюдения: возьмем произвольную формулу из конъюнктивная нормальная форма, который, в частности, представляет собой схему глубины-2. Теперь лемма о переключении гарантирует, что после задания некоторых переменных случайным образом мы получим булеву функцию, которая зависит только от нескольких переменных, т.е. ее можно вычислить с помощью Древо решений небольшой глубины ${\displaystyle d}$. Это позволяет нам записать ограниченную функцию в виде небольшой формулы в дизъюнктивная нормальная форма. Таким образом, формула в конъюнктивной нормальной форме, пораженная случайным ограничением переменных, может быть «переключена» на небольшую формулу в дизъюнктивной нормальной форме.

Оригинальное доказательство леммы о переключениях (Хостад 1987 ) включает спор с условные вероятности Возможно более простые доказательства были впоследствии даны Разборов (1993) и Луч (1994). Для введения см. Главу 14 в Арора и Барак (2009).

Рекомендации

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