Белла Субботовская

Белла Абрамовна Субботовская
Белла Абрамовна Субботовская
Субботовская в 1961 году
Рожденный	( 1937-12-17 )17 декабря 1937 г. Москва , Россия
Умер	23 ноября 1982 г. (1982-11-23)(44 года)
Причина смерти	Автокатастрофа (предполагаемое убийство )
Место отдыха	Востряковское еврейское кладбище, Москва
Национальность	Русский
Альма-матер	Механико-математический факультет Московского государственного университета им.
Известный	Сложность булевой формулы Еврейский народный университет
Супруг	Илья Мучник ​ ( м.  1961–1971 )
Научная карьера
Поля	Математическая логика Математическое образование
Тезис	«Критерий сравнимости базисов для реализации булевых функций формулами»  (1963)
Научные консультанты	Олег Лупанов

Белла Абрамовна Субботовская (17 декабря 1937 г. – 23 сентября 1982 г.) ^[1] была советским математиком, основавшим недолго просуществовавший Еврейский народный университет (1978–1983 гг.) в Москве . ^{[2] [3]} Целью школы было предоставление бесплатного образования тем, кто пострадал от структурированного антисемитизма в советской образовательной системе. Ее существование было за пределами советской власти, и ее расследовал КГБ . Сама Субботовская несколько раз подвергалась допросам со стороны КГБ и вскоре после этого была сбита грузовиком и погибла, что, как предполагалось, было убийством . [ ^4]

До основания Еврейского народного университета Субботовская опубликовала работы по математической логике . Ее результаты по булевым формулам, записанным в терминах , и оказали влияние на тогда еще зарождающуюся область теории вычислительной сложности .${\displaystyle \земля}$${\displaystyle \лор }$${\displaystyle \lnot}$

Субботовская изобрела метод случайных ограничений для булевых функций . ^[5] Начиная с функции , ограничение представляет собой частичное присвоение к переменных , дающее функцию от меньшего числа переменных. Возьмем следующую функцию:${\displaystyle f}$${\displaystyle \ро}$${\displaystyle f}$${\displaystyle нк}$${\displaystyle n}$${\displaystyle f_{\rho}}$

${\displaystyle f(x_{1},x_{2},x_{3})=(x_{1}\lor x_{2}\lor x_{3})\land (\lnot x_{1}\lor x_{2})\land (x_{1}\lor \lnot x_{3})}$.

Ниже приведено ограничение одной переменной.

${\displaystyle f_{\rho }(y_{1},y_{2}) = f(1,y_{1},y_{2})=(1\lor y_{1}\lor y_{2}) \land (\lnot 1\lor y_{1})\land (1\lor \lnot y_{2})}$.

При обычных тождествах булевой алгебры это упрощается до .${\displaystyle f_{\rho }(y_{1},y_{2})=y_{1}}$

Для выборки случайного ограничения сохраните переменные равномерно случайным образом. Для каждой оставшейся переменной присвойте ей 0 или 1 с равной вероятностью.${\displaystyle к}$

Как показано в приведенном выше примере, применение ограничения к функции может значительно сократить размер ее формулы. Хотя она написана с 7 переменными, ограничивая только одну переменную, мы обнаружили, что она использует только 1.${\displaystyle f}$${\displaystyle f_{\rho}}$

Субботовская доказала нечто гораздо более сильное: если — случайное ограничение переменных, то ожидаемое сокращение между и велико, в частности${\displaystyle \ро}$${\displaystyle нк}$${\displaystyle f}$${\displaystyle f_{\rho}}$

${\displaystyle \mathbb {E} \left[L(f_{\rho })\right]\leq \left({\frac {k}{n}}\right)^{3/2}L(f)}$,

где - минимальное число переменных в формуле. ^[5] Применяя неравенство Маркова, видим${\displaystyle L}$

${\displaystyle \Pr \left[L(f_{\rho })\leq 4\left({\frac {k}{n}}\right)^{3/2}L(f)\right]\geq {\frac {3}{4}}}$.

Возьмем в качестве функции четности по переменным. После применения случайного ограничения переменных мы знаем, что либо либо в зависимости от четности присвоений оставшимся переменным. Таким образом, очевидно, что размер вычисляющей схемы равен ровно 1. Затем, применяя вероятностный метод , для достаточно большого , мы знаем, что есть некоторые , для которых${\displaystyle f}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle f_{\rho}}$${\displaystyle x_{i}}$${\displaystyle \lnot x_{i}}$${\displaystyle f_{\rho}}$${\displaystyle n}$${\displaystyle \ро}$

${\displaystyle L(f_{\rho })\leq 4\left({\frac {1}{n}}\right)^{3/2}L(f)}$.

Подставляя , мы видим, что . Таким образом, мы доказали, что наименьшая схема для вычисления четности переменных, использующая только , должна использовать по крайней мере это количество переменных. ^[6]${\displaystyle L(f_{\rho})=1}$${\displaystyle L(f)\geq n^{3/2}/4}$${\displaystyle n}$${\ displaystyle \ земля, \ лор, \ lnot}$

Хотя это не исключительно сильная нижняя граница, случайные ограничения стали важным инструментом в сложности. В том же ключе к этому доказательству показатель в основной лемме был увеличен путем тщательного анализа до Патерсона и Цвика (1993), а затем до Хостада ( 1998). ^{[5] Кроме того,} лемма о переключении Хостада (1987) применила ту же технику к гораздо более богатой модели булевых схем постоянной глубины .${\displaystyle 3/2}$${\displaystyle 1.63}$${\displaystyle 2}$