Razborov, Alexandr Alexandrovič

Aleksandr Aleksandrovich Razborov (narozen 16. února 1963 , Belovo , Kemerovská oblast ) je ruský a americký matematik , člen korespondenta Ruské akademie věd (od roku 2000) [1] , specialista v oblasti teorie výpočtů . Má Erdősovo číslo 2. [2]

Životopis

Absolvent Moskevské fyzikální a matematické školy č. 2 (1980). Absolvent Fakulty mechaniky a matematiky Moskevské státní univerzity (1987). Kandidát fyzikálních a matematických věd (1987). Doktor fyzikálních a matematických věd (1991). V letech 1991 až 2008 působil v Matematickém ústavu. V. A. Steklov RAS . V letech 2001-2006 byl stálým členem Institutu pro pokročilé studium na Princetonské univerzitě [3] .

Od roku 2008 - čestný profesor na University of Chicago (USA) [4] [5] .

Dne 26. května 2000 byl zvolen členem korespondentem Ruské akademie věd na katedře matematických věd.

Vědecké výsledky

Ve své nejslavnější práci, kterou napsal se Stevenem Rudichem, představil koncept „natural proofs“ , třídu strategií používaných k prokázání základních spodních hranic v definici výpočetní složitosti . Zejména Razborov a Rudich ukázali, že za předpokladu, že existují určité druhy jednosměrných funkcí , takové důkazy nemohou poskytnout řešení problému P = NP , takže k vyřešení tohoto problému bude třeba vyvinout nové důkazové metody. Požadované.

Ceny a ceny

• Zlatá medaile Mezinárodní matematické olympiády v Londýně (1979).
• Nevanlinna Prize (1990) za „novou přibližnou metodu řešení algoritmických problémů“ [6]
• Gödelova cena (2007) (sdílená se Stevenem Rudichem) za jeho práci na „přirozených důkazech“. [7] [8]
• Čestný profesor (2008) Fakulty informatiky. Andrew MacLeish z University of Chicago , USA.

Bibliografie

• Razborov, A. A. Dolní hranice pro monotónní složitost některých booleovských funkcí  (anglicky)  // Zprávy Akademie věd  : časopis. - 1985. - Sv. 31 . - str. 354-357 .
• Razborov, A. A. Dolní hranice pro monotónní složitost logického permanentu  // Matematické poznámky Akademie věd SSSR: časopis. - 1985. - Červen ( roč. 37 , č. 6 ). - S. 485-493 . - doi : 10.1007/BF01157687 . (Ruština)
• Razborov, Alexander A. O soustavách rovnic ve volné skupině . - Moskevská státní univerzita , 1987.  (Ruština) (Ph.D. práce. 32,56 MB)
• Razborov, A. A. Dolní hranice pro složitost implementace symetrických booleovských funkcí obvody kontaktních hradel  // Matematické poznámky Akademie věd SSSR: časopis. - 1987. - Duben ( roč. 41 , č. 4 ). - S. 333-338 . - doi : 10.1007/BF01137685 . (Ruština)
• Razborov, Alexander A. (1989). „O metodě aproximace“ (PDF. 1,41 MB ) . Sborník příspěvků z 21. výročního sympozia ACM o teorii výpočetní techniky . Seattle, Washington (stát USA), Spojené státy americké. str. 167-176. DOI : 10.1145/73007.73023 . Použitý zastaralý parametr |month=( help );Neznámý parametr |Month=(navrženo |month=) ( nápověda v angličtině )
• Razborov, AA Dolní hranice složitosti symetrických booleovských funkcí obvodů kontakt-usměrňovač  (anglicky)  // Mathematical Notes  : journal. - 1990. - prosinec ( roč. 48 , č. 6 ). - S. 1226-1234 . - doi : 10.1007/BF01240265 .
• Razborov, Alexander A.; Rudich, Stephen (květen 1994). „Přirozené důkazy“ (PostScript) . Sborník příspěvků z 26. výročního sympozia ACM o teorii výpočetní techniky . Montreal, Quebec, Kanada. str. 204-213. DOI : 10.1145/195058.195134 . Použitý zastaralý parametr |month=( nápověda )
• Razborov, Alexander A. Dolní hranice polynomiálního počtu  (neopr.)  // Computational Complexity. - 1998. - prosinec ( vol. 7 , č. 4 ). - S. 291-324 . - doi : 10.1007/s000370050013 .
• Razborov, Alexander A. Propositional proof complexity  (anglicky)  // Journal of the ACM  : journal. - 2003. - Leden ( roč. 50 , č. 1 ). - str. 80-82 . - doi : 10.1145/602382.602406 . (Průzkumný materiál k 50. výročí JACM)
• Razborov A. A. Algebraická složitost. — M .: MTsNMO , 2016. — 32 s. - ISBN 978-5-4439-1032-1 .

Viz také

• volná skupina
• Jednosměrná funkce
• Pravidlo rozlišení

Poznámky

1. ↑ Razborov A.A. - Všeobecné informace . Získáno 3. ledna 2013. Archivováno z originálu dne 24. srpna 2017. (neurčitý)
2. ↑ Seznam osob s Erdős číslem 2 . Získáno 14. listopadu 2011. Archivováno z originálu 19. dubna 2019. (neurčitý)
3. ↑ Informatika a diskrétní matematika (CSDM) . Získáno 22. března 2021. Archivováno z originálu dne 23. března 2021. (neurčitý)
4. ↑ Životopis . Získáno 22. března 2021. Archivováno z originálu dne 31. října 2021. (neurčitý)
5. ↑ Katedra informatiky . Získáno 12. listopadu 2013. Archivováno z originálu 25. srpna 2013. (neurčitý)
6. ↑ Mezinárodní matematická unie: Vítězové ceny Rolfa Nevanlinny (odkaz není dostupný) . Získáno 14. listopadu 2011. Archivováno z originálu 18. října 2007. (neurčitý) 
7. ↑ Godelova cena 2007 (odkaz není k dispozici) . Získáno 12. dubna 2018. Archivováno z originálu 3. března 2016. (neurčitý) 
8. ↑ Gödelova cena - 2007 . Získáno 12. dubna 2018. Archivováno z originálu 12. dubna 2018. (neurčitý)

Odkazy

• Profil Alexandra Alekseeviče Razborova na oficiálních stránkách Ruské akademie věd
• Razborov Alexander Alexandrovič na webových stránkách All-Russian Mathematical Portal
• Osobní stránka A. A. Razborova
• Náčrt životopisu v Toyota Technological Institute v Chicagu.
• Životopisy na katedře informatiky, University of Chicago.
• DBLP: Alexander A. Razborov .
• Práce AA Razborova  — článek László Lovásze ve sborníku Mezinárodního kongresu matematiků , Kyoto, Japonsko, 1990.

Tematické stránky	Matematická genealogie Scopus zbMATH Otevřeno Všeruský matematický portál
Slovníky a encyklopedie	Universalis
V bibliografických katalozích	VIAF : 315943715 WorldCat VIAF : 315943715