Bella Subbotovskaya

matemático ruso

Bella Abramovna Subbotovskaya (17 de diciembre de 1937 - 23 de septiembre de 1982) ^[1] fue una matemática soviética que fundó la efímera Universidad del Pueblo Judío (1978-1983) en Moscú . ^{[2] [3]} El propósito de la escuela era ofrecer educación gratuita a aquellos afectados por el antisemitismo estructurado dentro del sistema educativo soviético. Su existencia quedó fuera de la autoridad soviética y fue investigada por la KGB . La propia Subbotovskaya fue interrogada varias veces por la KGB y poco después fue atropellada por un camión y murió, en lo que se ha especulado fue un asesinato . ^[4]

Trabajo académico

Antes de fundar la Universidad del Pueblo Judío, Subbotovskaya publicó artículos sobre lógica matemática . Sus resultados sobre fórmulas booleanas escritas en términos de , y fueron influyentes en el entonces naciente campo de la teoría de la complejidad computacional . ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle \lnot }$

Restricciones aleatorias

Subbotovskaya inventó el método de restricciones aleatorias a funciones booleanas . ^[5] Comenzando con una función , una restricción de es una asignación parcial de las variables, dando una función de menos variables. Tome la siguiente función: ${\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})}$.

La siguiente es una restricción de una variable.

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

Bajo las identidades habituales del álgebra booleana, esto se simplifica a . ${\displaystyle f_{\rho }(y_{1},y_{2})=y_{1}}$

Para muestrear una restricción aleatoria, retenga las variables uniformemente al azar. Para cada variable restante, asígnele 0 o 1 con igual probabilidad. ${\displaystyle k}$

Tamaño de la fórmula y restricciones

Como se demuestra en el ejemplo anterior, aplicar una restricción a una función puede reducir enormemente el tamaño de su fórmula. Aunque está escrito con 7 variables, al restringir solo una variable, encontramos que usa solo 1. ${\displaystyle f}$ ${\displaystyle f_{\rho }}$

Subbotovskaya demostró algo mucho más contundente: si se trata de una restricción aleatoria de variables, entonces la contracción esperada entre y es grande, específicamente ${\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)}$,

donde es el número mínimo de variables en la fórmula. ^[5] Aplicando la desigualdad de Markov vemos ${\displaystyle L}$

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

Aplicación de ejemplo

Considere la función de paridad sobre variables. Después de aplicar una restricción aleatoria de variables, sabemos que depende de la paridad de las asignaciones a las variables restantes. Así claramente el tamaño del circuito que calcula es exactamente 1. Luego aplicando el método probabilístico , para suficientemente grande , sabemos que hay algo para el cual ${\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)}$.

Al conectarnos , vemos eso . Por lo tanto, hemos demostrado que el circuito más pequeño para calcular la paridad de variables usando solo debe usar al menos esta cantidad de variables. ^[6] ${\displaystyle L(f_{\rho })=1}$ ${\displaystyle L(f)\geq n^{3/2}/4}$ ${\displaystyle n}$ ${\displaystyle \land ,\lor ,\lnot }$

Influencia

Aunque éste no es un límite inferior excepcionalmente fuerte, las restricciones aleatorias se han convertido en una herramienta esencial en la complejidad. De manera similar a esta prueba, el exponente en el lema principal ha sido incrementado mediante un análisis cuidadoso por Paterson y Zwick ( 1993) y luego por Håstad (1998). ^{[5] Además,} el lema de conmutación de Håstad (1987) aplicó la misma técnica al modelo mucho más rico de circuitos booleanos de profundidad constante . ${\displaystyle 3/2}$ ${\displaystyle 1.63}$ ${\displaystyle 2}$

Referencias

1. O'Connor, J; Robertson, E. "Bella Abramovna Subbotovskaya". MacTutor Historia de las Matemáticas . Escuela de Matemáticas y Estadística, Universidad de St Andrews, Escocia . Consultado el 9 de abril de 2024 .
2. Szpiro, G. (2007), "Bella Abramovna Subbotovskaya y la Universidad del Pueblo Judío", Avisos de la Sociedad Matemática Estadounidense , 54 (10), 1326-1330.
3. Zelevinsky, A. (2005), "Recordando a Bella Abramovna", reprobó su examen de matemáticas, camarada Einstein (M. Shifman, ed.), World Scientific , 191-195.
4. "Recordando a la heroína de las matemáticas Bella Abramovna Subbotovskaya". Matemáticas en las noticias . Asociación Matemática de América . 12 de noviembre de 2007 . Consultado el 28 de junio de 2014 .
5. Jukna, Stasys (6 de enero de 2012). Complejidad de la función booleana: avances y fronteras . Medios de ciencia y negocios de Springer. págs. 167-173. ISBN 978-3642245084.
6. Kulikov, Alejandro. "Minicurso sobre complejidad de circuitos: el exponente de contracción de fórmulas sobre U2" (PDF) . Consultado el 22 de enero de 2017 .