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

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

${\ Displaystyle \ ехр \ влево (\ Омега \ влево (п ^ {\ гидроразрыва {1} {к-1}} \ вправо) \ вправо)}$

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

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

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

Ссылки [ править ]