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

Белла Абрамовна Субботовская
Белла Абрамовна Субботовская
Субботовская в 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 \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}}$.

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

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

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

Субботовская доказала гораздо более сильное: если ${\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)}$,

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

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

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

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

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

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

Влияние

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

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

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