Bella Subbotovskaya

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

Bella Abramovna Subbotovskaya (17 December 1937 – 23 September 1982) был советским математиком, основавшим недолговечный Еврейский народный университет (1978–1983) в Москве . Целью школы было предложить бесплатное образование тем, кто пострадал от структурированного антисемитизма в советской системе образования. Его существование находилось за пределами советской власти и расследовалось КГБ . Сама Субботовская несколько раз допрашивалась в КГБ, вскоре после этого ее сбил грузовик и она умерла, что, как предполагалось, было покушением .

Академическая работа

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

Случайные ограничения

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

$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})$.

Ниже приводится ограничение одной переменной

$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})$.

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

Чтобы выбрать случайное ограничение, сохраните $k$ переменные равномерно случайным образом. Каждой оставшейся переменной присвойте ей 0 или 1 с равной вероятностью.

Размер формулы и ограничения

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

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

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

где $L$ — минимальное количество переменных в формуле. Применяя неравенство Маркова, мы видим

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

Пример приложения

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

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

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

Влияние

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