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

русский математик

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

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

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

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

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

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

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

Субботовская доказала нечто гораздо более сильное: если — случайное ограничение переменных, то ожидаемое сокращение между и велико, в частности ${\displaystyle \rho }$ ${\displaystyle n-k}$ ${\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 \rho }$

${\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 \land ,\lor ,\lnot }$

Влияние

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

Ссылки

1. О'Коннор, Дж.; Робертсон, Э. «Белла Абрамовна Субботовская». История математики MacTutor . Школа математики и статистики, Университет Сент-Эндрюс, Шотландия . Получено 9 апреля 2024 г.
2. Szpiro, G. (2007), «Белла Абрамовна Субботовская и Еврейский народный университет», Notices of the American Mathematical Society , 54 (10), 1326–1330.
3. Зелевинский, А. (2005), «Вспоминая Беллу Абрамовну», Вы провалили тест по математике, товарищ Эйнштейн (ред. М. Шифман), World Scientific , 191–195.
4. "Вспоминая героиню математики Беллу Абрамовну Субботовскую". Математика в новостях . Математическая ассоциация Америки . 12 ноября 2007 г. Получено 28 июня 2014 г.
5. Jukna, Stasys (6 января 2012 г.). Сложность булевых функций: достижения и рубежи . Springer Science & Business Media. стр. 167–173. ISBN 978-3642245084.
6. Куликов, Александр. "Миникурс по сложности схем: показатель сокращения формул над U2" (PDF) . Получено 22 января 2017 г. .