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 los afectados por el antisemitismo estructurado dentro del sistema educativo soviético. Su existencia estaba 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]
Bella Abramovna Subbotovskaya | |
---|---|
Белла Абрамовна Субботовская | |
![]() Subbotovskaya en 1961 | |
Nació | |
Fallecido | 23 de noviembre de 1982 | (44 años)
Causa de la muerte | Accidente automovilístico (presunto asesinato ) |
Lugar de descanso | Cementerio judío de Vostryakovo, Moscú |
Nacionalidad | ruso |
alma mater | Facultad de Mecánica y Matemáticas , Universidad Estatal de Moscú |
Conocido por | Fórmula booleana complejidad Universidad del Pueblo Judío |
Esposos) | Ilya Muchnik ( m. 1961 – 1971) |
Carrera científica | |
Campos | Lógica matemática Educación matemática |
Tesis | "Un criterio para la comparabilidad de bases para la realización de funciones booleanas por fórmulas" (1963) |
Asesores académicos | Oleg Lupanov |
Trabajo académico
Antes de fundar la Universidad del Pueblo Judío, Subbotovskaya publicó artículos sobre lógica matemática . Sus resultados en 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 las funciones booleanas . [5] Comenzando con una función, una restricción de es una cesión parcial a de El variables, dando una función de menos variables. Toma la siguiente función:
- .
La siguiente es una restricción de una variable
- .
Bajo las identidades habituales del álgebra de Boole, esto se simplifica a.
Para muestrear una restricción aleatoria, conserve variables uniformemente al azar. Para cada variable restante, asígnele 0 o 1 con la misma probabilidad.
Restricciones y tamaño de la fórmula
Como se demostró 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 utiliza solo 1.
Subbotovskaya demostró algo mucho más fuerte: si es una restricción aleatoria de variables, entonces la contracción esperada entre y es grande, específicamente
- ,
dónde es el número mínimo de variables en la fórmula. [5] Aplicando la desigualdad de Markov vemos
- .
Aplicación de ejemplo
Llevar para ser la función de paridad sobrevariables. Después de aplicar una restricción aleatoria de variables, sabemos que es cualquiera o dependiendo de la paridad de las asignaciones al resto de variables. Así, claramente, el tamaño del circuito que calculaes exactamente 1. Luego, aplicando el método probabilístico , para lo suficientemente grande, sabemos que hay algunos para cual
- .
Conectando , vemos eso . Por tanto, hemos probado que el circuito más pequeño para calcular la paridad de variables usando solo debe utilizar al menos esta cantidad de variables. [6]
Influencia
Aunque este no es un límite inferior excepcionalmente fuerte, las restricciones aleatorias se han convertido en una herramienta esencial en la complejidad. En una línea similar a esta prueba, el exponente en el lema principal se ha incrementado mediante un análisis cuidadoso para por Paterson y Zwick (1993) y luego apor Håstad (1998). [5] Además, el lema Switching 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" . Archivo MacTutor History of Mathematics . Escuela de Matemáticas y Estadística, Universidad de St Andrews, Escocia . Consultado el 22 de enero de 2017 .
- ^ 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", Falló su prueba de matemáticas Camarada Einstein (M. Shifman, ed.), World Scientific , 191-195.
- ^ "Recordando a la heroína matemática 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 .
- ^ a b c Jukna, Stasys (6 de enero de 2012). Complejidad de funciones booleanas: avances y fronteras . Springer Science & Business Media. págs. 167-173. ISBN 978-3642245084.
- ^ Kulikov, Alexander. "Minicurso de complejidad de circuito: el exponente de contracción de fórmulas sobre U2" (PDF) . Consultado el 22 de enero de 2017 .