Bella Subbotovskaya - Bella Subbotovskaya
Bella Abramovna Subbotovská | |
---|---|
Белла Абрамовна Субботовская | |
Subbotovskaya v roce 1961 | |
narozený | |
Zemřel | 23. listopadu 1982 | (ve věku 44)
Příčina smrti | Bouračka (podezření atentát ) |
Odpočívadlo | Vostryakovo židovský hřbitov, Moskva |
Národnost | ruština |
Alma mater | Fakulta mechaniky a matematiky, Moskevská státní univerzita |
Známý jako | Složitost booleovského vzorce Židovská lidová univerzita |
Manžel (y) | Ilya Muchnik (m. 1961–1971) |
Vědecká kariéra | |
Pole | Matematická logika Matematické vzdělávání |
Teze | "Kritérium srovnatelnosti základen pro realizaci booleovských funkcí pomocí vzorců" (1963) |
Akademičtí poradci | Oleg Lupanov |
Bella Abramovna Subbotovskaya (17. prosince 1937-23. Září 1982)[1] byl sovětský matematik, který založil krátkodobé Židovská lidová univerzita (1978–1983) v Moskva.[2][3] Účelem školy bylo nabídnout bezplatné vzdělání osobám zasaženým strukturovaným antisemitismem v rámci sovětského vzdělávacího systému. Jeho existence byla mimo sovětskou autoritu a byla vyšetřována KGB. Sama Subbotovskaya byla několikrát vyslýchána KGB a krátce nato byla sražena kamionem a zahynula. atentát.[4]
Akademická práce
Před založením Židovské lidové univerzity publikovala Subbotovskaya v roce matematická logika. Její výsledky týkající se booleovských vzorců napsané z hlediska , , a měli vliv na tehdy rodící se pole teorie výpočetní složitosti.
Náhodná omezení
Subbotovskaya vynalezl metodu náhodných omezení Booleovské funkce.[5] Počínaje funkcí , omezení z je částečný úkol pro z proměnné, které dávají funkci méně proměnných. Vezměte následující funkci:
- .
Následuje omezení jedné proměnné
- .
Pod obvyklou identitou Booleova algebra tím se zjednodušuje .
Chcete-li ochutnat náhodné omezení, ponechejte proměnné rovnoměrně náhodně. Pro každou zbývající proměnnou jej přiřaďte se stejnou pravděpodobností 0 nebo 1.
Velikost vzorce a omezení
Jak je ukázáno ve výše uvedeném příkladu, použití omezení na funkci může masivně zmenšit velikost jejího vzorce. Ačkoli je zapsán se 7 proměnnými, omezením pouze jedné proměnné jsme to zjistili používá pouze 1.
Subbotovská prokázala něco mnohem silnějšího: pokud je náhodné omezení proměnné, pak očekávané zmenšení mezi a je velký, konkrétně
- ,
kde je minimální počet proměnných ve vzorci.[5] Přihlašování Markovova nerovnost vidíme
- .
Příklad aplikace
Vzít být paritní funkce přes proměnné. Po uplatnění náhodného omezení proměnné, to víme je buď nebo v závislosti na paritě přiřazení ke zbývajícím proměnným. Jasně tedy velikost obvodu, který se počítá je přesně 1. Pak použijte pravděpodobnostní metoda, pro dostatečně velké , víme, že tam nějaké jsou pro který
- .
Připojování , vidíme to . Tak jsme dokázali, že nejmenší obvod pro výpočet parity pouze pomocí proměnných musí používat alespoň tolik proměnných.[6]
Vliv
Ačkoli se nejedná o výjimečně silnou dolní mez, náhodná omezení se staly základním nástrojem složitosti. V podobném duchu jako tento důkaz, exponent v hlavním lematu byla zvýšena pečlivou analýzou na podle Paterson a Zwick (1993) a poté podle Håstad (1998).[5]Navíc Håstad's Přepínání lemmatu (1987) aplikovali stejnou techniku na mnohem bohatší model konstantní hloubky Booleovské obvody.
Reference
- ^ O'Connor, J; Robertson, E. „Bella Abramovna Subbotovskaya“. MacTutor Historie archivu matematiky. Škola matematiky a statistiky, University of St Andrews, Skotsko. Citováno 22. ledna 2017.
- ^ Szpiro, G. (2007), "Bella Abramovna Subbotovskaya a Židovská lidová univerzita ", Oznámení Americké matematické společnosti, 54(10), 1326–1330.
- ^ Zelevinsky, A. (2005), „Remembering Bella Abramovna“, Zklamal jste matematické zkoušky, soudruhu Einsteine (M. Shifman, ed.), World Scientific, 191–195.
- ^ „Vzpomínka na matematickou hrdinku Bellu Abramovnu Subbotovskou“. Matematika ve zprávách. Mathematical Association of America. 12. listopadu 2007. Citováno 28. června 2014.
- ^ A b C Jukna, Stasys (6. ledna 2012). Boolean Function Complexity: Advances and Frontiers. Springer Science & Business Media. 167–173. ISBN 978-3642245084.
- ^ Kulikov, Alexander. „Minikurza složitosti obvodu: Smršťovací exponent vzorců nad U2“ (PDF). Citováno 22. ledna 2017.