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 .
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:
- .
La siguiente es una restricción de una variable.
- .
Bajo las identidades habituales del álgebra booleana, esto se simplifica a .
Para muestrear una restricción aleatoria, retenga las variables uniformemente al azar. Para cada variable restante, asígnele 0 o 1 con igual probabilidad.
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.
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
- ,
donde es el número mínimo de variables en la fórmula. [5] Aplicando la desigualdad de Markov vemos
- .
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
- .
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]
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 .
Referencias
- ^ 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 .
- ^ Szpiro, G. (2007), "Bella Abramovna Subbotovskaya y la Universidad del Pueblo Judío", Avisos de la Sociedad Matemática Estadounidense , 54 (10), 1326-1330.
- ^ Zelevinsky, A. (2005), "Recordando a Bella Abramovna", reprobó su examen de matemáticas, camarada Einstein (M. Shifman, ed.), World Scientific , 191-195.
- ^ "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 .
- ^ abc 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.
- ^ 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 .