Bella Subbotovskaya

Bella Abramovna Subbotovskaya
Белла Абрамовна Суботовская
Subbotovskaya w 1961 roku
Urodzić się	( 17.12.1937 ) 17 grudnia 1937 Moskwa , Rosja
Zmarł	23 listopada 1982 ( w wieku 44) ( 23.11.1982 )
Przyczyną śmierci	Wypadek samochodowy (podejrzenie zabójstwa )
Miejsce odpoczynku	Cmentarz żydowski Wostryakowo, Moskwa
Narodowość	Rosyjski
Alma Mater	Wydział Mechaniki i Matematyki Moskiewskiego Uniwersytetu Państwowego
Znany z	Złożoność formuł boolowskich Żydowski Uniwersytet Ludowy
Współmałżonek	Ilja Muchnik ​ ( m. 1961–1971 <a i=3>) ​
Kariera naukowa
Pola	Logika matematyczna Edukacja matematyczna
Praca dyplomowa	„Kryterium porównywalności podstaw do realizacji funkcji boolowskich za pomocą wzorów” (1963)
Doradcy akademiccy	Oleg Łupanow

Bella Abramovna Subbotovskaya (17 grudnia 1937 - 23 września 1982) była sowiecką matematyczką, która założyła krótkotrwały Żydowski Uniwersytet Ludowy (1978–1983) w Moskwie . Celem szkoły było oferowanie bezpłatnej edukacji osobom dotkniętym zorganizowanym antysemityzmem w sowieckim systemie edukacyjnym. Jego istnienie było poza władzą sowiecką i było badane przez KGB . Sama Subbotovskaya była wielokrotnie przesłuchiwana przez KGB, a wkrótce potem została potrącona przez ciężarówkę i zginęła, co, jak spekulowano, było zamachem .

Praca akademicka

Przed założeniem Żydowskiego Uniwersytetu Ludowego Subbotovskaya publikowała artykuły z logiki matematycznej . $zapisanych$ w terminach $złożoności$ i $wpływ$ miały na rodzącą się wówczas dziedzinę teorii obliczeniowej .

Losowe ograniczenia

Subbotovskaya wynalazła metodę losowych ograniczeń funkcji boolowskich . $\ displaystyle$ od funkcji , ograniczeniem $displaystyle nk}$ częściowe przypisanie do zmiennych n $rho$$ρ$ \ $\$ dając funkcję mniejszej liczby zmiennych. ${\ displaystyle f _ {\ rho}}$ Weź następującą funkcję:

${\ Displaystyle f (x_ {1}, x_{2},x_{3})=(x_{1}\lor x_{2}\lor x_{3})\kraj (\lnot x_{1}\lor x_{2})\kraj (x_{ 1}\lor \lnot x_{3})}$ .

Poniżej znajduje się ograniczenie jednej zmiennej

${\ Displaystyle f_ {\rho}(y_{1},y_{2})=f(1,y_{1},y_{2})=(1\lor y_{1}\lor y_{2})\kraj (\ lnot 1\lor y_{1})\land (1\lor \lnot y_{2})}$ .

W przypadku zwykłych tożsamości algebry Boole'a upraszcza się to do ${\ Displaystyle f _ {\ rho} (y_ {1}, y_ {2}) = y_ {1}}$ .

Aby próbkować losowe ograniczenie, zachowaj $równomiernie$ losowo. Każdej pozostałej zmiennej przypisz z równym prawdopodobieństwem 0 lub 1.

Rozmiar formuły i ograniczenia

Jak pokazano w powyższym przykładzie, zastosowanie ograniczenia do funkcji może znacznie zmniejszyć rozmiar jej formuły. Chociaż $zapisany$ z 7 zmiennymi, ograniczając tylko jedną zmienną, stwierdziliśmy, że używa tylko 1. $} .$

$}}$ coś znacznie silniejszego: jeśli $jest$ ograniczeniem $zmiennych$ , to oczekiwany skurcz między fa $\ displaystyle f _$$\ rho$ jest szczególnie duży

${\ Displaystyle \ mathbb {E} \ lewo [L (f _ {\ rho}) \ prawej] \ równoważnik \ lewo ({\ Frac {k}{n}}\right)^{3/2}L(f)}$ ,

gdzie jest $.$ liczbą zmiennych we wzorze Stosując nierówność Markowa widzimy

${\ Displaystyle \ Pr \ lewo [L (f_ {\ rho}) \ równoważnik 4 \ lewo ({\ Frac { k}{n}}\right)^{3/2}L(f)\right]\geq {\frac {3}{4}}}$ .

Przykład zastosowania

Weźmy funkcję $_$ nad $_ Po$ . _ $displaystyle x_ {i}$$zmiennych$ ograniczenia wiemy, że jest albo $\$ lub $\ displaystyle \lnot x_{i}}$ w zależności od parzystości przypisań do pozostałych zmiennych. Tak $\ rho }$ wyraźnie rozmiar obwodu, który oblicza, $dokładnie$ 1. Następnie stosując metodę probabilistyczną , dla wystarczająco dużego wiemy, że istnieje jakiś $displaystyle \$ dla którego

${\ Displaystyle L (f _ {\ rho}) \ równoważnik 4 \ lewo ({\ Frac {1} {n}} \ prawej) ^ { 3/2}L(f)}$ .

$L (f _ {\ rho}) = 1}$ Displaystyle , widzimy, że ${\ Displaystyle L (f) \ geq n ^ { 3/2}/4}$ . $przy$ ten sposób udowodniliśmy, że najmniejszy obwód do obliczania parzystości $tylko$ musi co najmniej tyle

Wpływ

Chociaż nie jest to wyjątkowo silna dolna granica, przypadkowe ograniczenia stały się podstawowym narzędziem w złożoności. W podobnym duchu do tego dowodu, wykładnik w głównym lemacie został zwiększony poprzez dokładną analizę $do$ Patersona i Zwicka ( 1993), a następnie $Displaystyle$$} displaystyle 2}$ autorstwa Håstad (1998). Dodatkowo, Lemat o przełączaniu Håstada (1987) zastosował tę samą technikę do znacznie bogatszego modelu obwodów boolowskich o stałej głębokości .