Ο Αλεξάντρ Αλεξάντροβιτς Ραζμπόροφ (Aleksandr Aleksandrovich Razborov, ρωσικά: Алекса́ндр Алекса́ндрович Разбо́ров, γεννηθείς στις 16 Φεβρουαρίου 1963), μερικές φορές γνωστός ως Σάσα Ραζμπόροφ, είναι Σοβιετικός και Ρώσος μαθηματικός και υπολογιστικός θεωρητικός. Είναι Καθηγητής Διακεκριμένης Υπηρεσίας Άντριου ΜακΛις στο Πανεπιστήμιο του Σικάγο.
Έρευνα
Το πιο γνωστό έργο του, από κοινού με τον Στίβεν Ρούντιτς, εισήγαγαν την έννοια των φυσικών αποδείξεων, μια τάξη στρατηγικών που χρησιμοποιούνται για να αποδείξουν τα θεμελιώδη κάτω όρια στην υπολογιστική πολυπλοκότητα. Ειδικότερα, ο Ραζμπόροφ και ο Ρούντιτς έδειξαν ότι, κάτω από την υπόθεση ότι ορισμένων ειδών μονόδρομων συναρτήσεων υπάρχουν τέτοιες αποδείξεις που δεν μπορούν να δώσουν λύση στο πρόβλημα P=NP, έτσι θα απαιτηθούν νέες τεχνικές για να λύσουν αυτό το ζήτημα.
Βραβεύσεις
Βραβείο Νεβάνλινα (1990) για την εισαγωγή της "μεθόδου προσέγγισης" στην απόδειξη των κάτω ορίων του κυκλώματος Μπουλίαν ορισμένων βασικών αλγοριθμικών προβλημάτων,[2]
Λέκτορας Έρντος, Εβραϊκό Πανεπιστήμιο της Ιερουσαλήμ, 1998.
Αντεπιστέλλον μέλος της Ρωσικής Ακαδημίας Επιστημών (2000)[3][4]
Βραβείο Ντέιβιντ Π. Ρόμπινς για το βιβλίο "Σχετικά με την ελάχιστη πυκνότητα των τριγώνων σε γραφήματα" (Συνδυαστική, Πιθανότητες και Πληροφορική 17 (2008), αριθ. 4, 603-618), και για την εισαγωγή μιας νέας ισχυρής μεθόδου, αναφοράς αλγεβρών, για να λύσει προβλήματα σε ακραία συνδυαστική
Βραβείο Γκέντελ (2007, με τον Στίβεν Ρούντιτς) για την εφημερίδα "Φυσικές Αποδείξεις."[5][6]
Καθηγητής Διακεκριμένης Υπηρεσίας Άντριου ΜακΛις (2008) στο Τμήμα Επιστήμης Υπολογιστών του Πανεπιστήμιου του Σικάγο.
Δείτε επίσης
Άβι Ουίγκντερσον
Πολυπλοκότητα κυκλώματος
Ελεύθερη ομάδα
Φυσικές αποδείξεις
Μονόδρομη λειτουργία
Ψευδοτυχαία οικογένεια εξίσωσης
Ψήφισμα (λογική)
Βιβλιογραφία
Razborov, A. A. (1985). «Lower bounds for the monotone complexity of some Boolean functions» (PDF). Soviet Mathematics - Doklady 31: 354–357.
Razborov, A. A. (June 1985). «Lower bounds on monotone complexity of the logical permanent». Mathematical Notes of the Academy of Sciences of the USSR 37 (6): 485–493. doi:10.1007/BF01157687.
Разборов, Александр Александрович (1987). (PDF) (στα Russian). Московский государственный университет http://www.mi.ras.ru/~razborov/phd.pdf. Missing or empty |title= (βοήθεια)CS1 maint: Μη αναγνωρίσιμη γλώσσα (link) (PhD thesis. 32.56MB)
Razborov, A. A. (April 1987). «Lower bounds on the size of bounded depth circuits over a complete basis with logical addition». Mathematical Notes of the Academy of Sciences of the USSR 41 (4): 333–338. doi:10.1007/BF01137685.
Razborov, Alexander A. (May 1989). «On the method of approximations» (PDF. 1.41MB). Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. Seattle, Washington, United States, pp. 167–176. doi:10.1145/73007.73023.
Razborov, A. A. (December 1990). «Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits». Mathematical Notes of the Academy of Sciences of the USSR 48 (6): 1226–1234. doi:10.1007/BF01240265.
Razborov, Alexander A.; Rudich, Stephen (May 1994). «Natural proofs» (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Canada, pp. 204–213. doi:10.1145/195058.195134.
Razborov, Alexander A. (December 1998). «Lower Bounds for the Polynomial Calculus» (PostScript). Computational Complexity 7 (4): 291–324. doi:10.1007/s000370050013.
Razborov, Alexander A. (January 2003). «Propositional proof complexity» (PostScript). Journal of the ACM 50 (1): 80–82. doi:10.1145/602382.602406. (Survey paper for JACM's 50th anniversary)
Παραπομπές
Ανακτήθηκε στις 3 Ιουλίου 2019.
«International Mathematical Union: Rolf Nevanlinna Prize Winners». Αρχειοθετήθηκε από το πρωτότυπο στις 17 Δεκεμβρίου 2007.
«Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History».
«Russian Genealogy Agencies Tree: R» (στα Russian). Αρχειοθετήθηκε από το πρωτότυπο στις 21 Δεκεμβρίου 2007. Ανακτήθηκε στις 4 Αυγούστου 2018.CS1 maint: Μη αναγνωρίσιμη γλώσσα (link)
«ACM-SIGACT Awards and Prizes: 2007 Gödel Prize».
«EATCS: Gödel Prize - 2007». Αρχειοθετήθηκε από το πρωτότυπο στις 1 Δεκεμβρίου 2007.
Εξωτερικοί σύνδεσμοι
Αλεξάντερ Ραζμπόροφ στο Mathematics Genealogy Project.
Alexander Razborov's Home Page.
All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich.
Biography sketch in the Toyota Technological Institute at Chicago.
Curricula Vitae at the Department of Computer Science, University of Chicago.
DBLP: Alexander A. Razborov.
Πρότυπο:IMO results
MathSciNet: "Items authored by Razborov, A. A."
The Work of A.A. Razborov – an article by László Lovász in the Proceedings of the International Congress of Mathematicians, Kyoto, Japan, 1990.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
