Λεονίντ Λέβιν

Λεονίντ Λέβιν
Γενικές πληροφορίες
Γέννηση2 Νοεμβρίου 1948
Ντνίπρο
Χώρα πολιτογράφησηςΗνωμένες Πολιτείες Αμερικής
Ένωση Σοβιετικών Σοσιαλιστικών Δημοκρατιών
Εκπαίδευση και γλώσσες
Ομιλούμενες γλώσσεςΑγγλικά
Εκπαίδευσηδιδάκτωρ φιλοσοφίας
ΣπουδέςΣχολή Μηχανικής και Μαθηματικών του Πανεπιστημίου της Μόσχας
Τεχνολογικό Ινστιτούτο Μασαχουσέτης (έως 1979)
Κρατικό Πανεπιστήμιο της Μόσχας[1]
Πληροφορίες ασχολίας
Ιδιότηταμαθηματικός
επιστήμονας υπολογιστών
ΕργοδότηςΠανεπιστήμιο της Βοστώνης (από 1980)
Αξιοσημείωτο έργοΘεώρημα Κουκ-Λέβιν
Αξιώματα και βραβεύσεις
Βραβεύσειςβραβείο Κνουθ (2012)
βραβείο Χούμπολτ (2010)
Υποτροφία Γκούγκενχαϊμ (1993)[2]
Commons page Σχετικά πολυμέσα
δεδομένα

Ο Λεονίντ Ανατόλιεβιτς Λέβιν (ρωσικά: Леонид Анатольевич Левин‎‎, ουκρανικά: Леонід Анатолійович Левін‎‎· γενν. 2 Νοεμβρίου 1948) είναι Σοβιετοαμερικανός μαθηματικός και επιστήμονας υπολογιστών. Είναι περισσότερο γνωστός για την ανακάλυψη της έννοιας της NP-πληρότητας παράλληλα με τον Στίβεν Κουκ και για αποτελέσματα που ενισχύουν τα θεωρήματα μη πληρότητας του Γκέντελ.

Είναι γνωστός για το έργο του στον τομέα της τυχαιότητας στην πληροφορική, της αλγοριθμικής πολυπλοκότητας και της δυσεπίλυτης πολυπλοκότητας, της πολυπλοκότητας μέσης περίπτωσης,[3] των θεμελίων των μαθηματικών και της επιστήμης των υπολογιστών, της αλγοριθμικής πιθανότητας, της θεωρίας του υπολογισμού και της θεωρίας της πληροφορίας. Πήρε το μεταπτυχιακό του δίπλωμα στο Πανεπιστήμιο της Μόσχας το 1970, όπου σπούδασε υπό τον Αντρέι Κολμογκόροφ και ολοκλήρωσε τις ακαδημαϊκές απαιτήσεις του Υποψήφιου Πτυχίου το 1972[4].

Ανακάλυψε ανεξάρτητα με τον Στίβεν Κουκ την ύπαρξη προβλημάτων NP-complete. Αυτό το θεώρημα της NP-πληρότητας, που συχνά αποκαλείται θεώρημα των Κουκ-Λεβίν, αποτέλεσε τη βάση για ένα από τα επτά Προβλήματα του Βραβείου της Χιλιετίας που ανακηρύχθηκαν από το Ινστιτούτο Μαθηματικών Clay με προσφερόμενο βραβείο 1.000.000 δολαρίων. Το θεώρημα Κουκ-Λέβιν ήταν μια σημαντική ανακάλυψη στην επιστήμη των υπολογιστών και ένα σημαντικό βήμα στην ανάπτυξη της θεωρίας της υπολογιστικής πολυπλοκότητας.

Ο Λέβιν τιμήθηκε με το βραβείο Κνουθ το 2012[5] για την ανακάλυψη της NP-πληρότητας και την ανάπτυξη της πολυπλοκότητας μέσης περίπτωσης. Είναι μέλος της Εθνικής Ακαδημίας Επιστημών των ΗΠΑ και μέλος της Αμερικανικής Ακαδημίας Τεχνών και Επιστημών.

Βιογραφία

[Επεξεργασία | επεξεργασία κώδικα]

Πήρε το μεταπτυχιακό του δίπλωμα στο Πανεπιστήμιο της Μόσχας το 1970, όπου σπούδασε υπό την καθοδήγηση του Αντρέι Κολμογκόροφ και ολοκλήρωσε τις απαιτήσεις για το πτυχίο του υποψηφίου το 1972[4][6] Αφού ερεύνησε αλγοριθμικά προβλήματα στη θεωρία της πληροφορίας στο Ινστιτούτο Μετάδοσης Πληροφοριών της Εθνικής Ακαδημίας Επιστημών της Μόσχας το 1972-1973 και ως ανώτερος ερευνητής στο Εθνικό Ερευνητικό Ινστιτούτο Ολοκληρωμένων Αυτοματισμών για τη Βιομηχανία Πετρελαίου και Φυσικού Αερίου της Μόσχας το 1973-1977, μετανάστευσε στις Ηνωμένες Πολιτείες το 1978 και απέκτησε διδακτορικό δίπλωμα στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης (ΜΙΤ) το 1979[4], υπό την επίβλεψη του Άλμπερτ Ρ. Μάγιερ.

Είναι γνωστός για το έργο του στον τομέα της τυχαιότητας στην πληροφορική, της αλγοριθμικής πολυπλοκότητας και της δυσεπίλυτης πολυπλοκότητας, της πολυπλοκότητας μέσης περίπτωσης,[3] των θεμελίων των μαθηματικών και της επιστήμης των υπολογιστών, της αλγοριθμικής πιθανότητας, της θεωρίας του υπολογισμού και της θεωρίας της πληροφορίας.

Η ζωή του περιγράφεται σε ένα κεφάλαιο του βιβλίου Out of Their Minds: Η ζωή και οι ανακαλύψεις 15 σπουδαίων επιστημόνων πληροφορικής.[7]

Ο Λέβιν και ο Στίβεν Κουκ ανακάλυψαν ανεξάρτητα την ύπαρξη NP-πλήρων προβλημάτων. Αυτό το θεώρημα πληρότητας NP, που συχνά αναφέρεται ως θεώρημα Κουκ-Λέβιν, αποτέλεσε τη βάση για ένα από τα επτά προβλήματα του Βραβείου της Χιλιετίας που ανακηρύχθηκε από το Ινστιτούτο Μαθηματικών Clay και τιμήθηκε με έπαθλο 1.000.000 δολαρίων. Το θεώρημα Κουκ-Λέβιν αποτέλεσε μια σημαντική ανακάλυψη στον τομέα της επιστήμης των υπολογιστών και ένα σημαντικό βήμα στην ανάπτυξη της θεωρίας πολυπλοκότητας των υπολογιστών. Η εργασία του Λέβιν για το θεώρημα αυτό δημοσιεύτηκε το 1973[8] - είχε ήδη δώσει διάλεξη για τις ιδέες που περιέχονται σε αυτό μερικά χρόνια νωρίτερα (βλ. την εργασία του Τρακτένμπροτ)[9] , αν και η πλήρης επίσημη συγγραφή των αποτελεσμάτων έγινε μετά τη δημοσίευση του Κουκ.

Ο Λέβιν τιμήθηκε με το βραβείο Κνουθ το 2012[5] για την ανακάλυψη της NP-πληρότητας και την ανάπτυξη της πολυπλοκότητας μέσης περίπτωσης.

Σήμερα είναι καθηγητής πληροφορικής στο Πανεπιστήμιο της Βοστώνης, όπου άρχισε να διδάσκει το 1980.

Εργασία σε θεωρήματα μη πληρότητας

[Επεξεργασία | επεξεργασία κώδικα]

Απέναντι σε μια υποτιθέμενα συνεκτική και ελλιπή θεωρία, όπως είναι τα αξιώματα του Πεάνο,[10] μια απλή ιδέα είναι η προσπάθεια ολοκλήρωσής της, επιλέγοντας για κάθε αναποφάσιστη δήλωση αυτής της θεωρίας να την ενσωματώσει ή να ενσωματώσει την άρνησή της. Η προκύπτουσα θεωρία μετά από έναν άπειρο αριθμό βημάτων θα είναι τότε πλήρης και ισοδύναμη με την αρχική θεωρία. Εάν αυτή η ιδέα δεν μπορεί να δώσει αποτελεσματικά, αναδρομικά, μια πλήρη θεωρία, είναι επειδή το ερώτημα εδώ -αν μια πρόταση είναι αποφασίσιμη ή όχι σε μια θεωρία είναι από μόνη της ένα πρόβλημα που δεν μπορεί να αποφασιστεί.

Ο Λέβιν δημοσίευσε αποτελέσματα το 2002 που δείχνουν ότι δεν μπορεί κανείς να προσπαθήσει να ολοκληρώσει ελλιπείς θεωρίες, χρησιμοποιώντας τη φυσική, κβαντική τύχη για να αποφασίσει για κάθε αναποφάσιστη δήλωση της θεωρίας αν αυτή προστίθεται ή αναιρείται για να σχηματίσει μια πλήρη θεωρία.

Αυτό που αποδεικνύει ο Λέβιν είναι πρώτον ότι οποιοσδήποτε πιθανοτικός αλγόριθμος που δίνει μια συνεπή και πλήρη επέκταση της αριθμητικής του Πεάνο θα έχει άπειρες πληροφορίες για το πρόβλημα της διακοπής και δεύτερον ότι ένας πιθανοτικός αλγόριθμος δεν μπορεί να λύσει το πρόβλημα της διακοπής.

Εκτός από αυτά τα αποδεδειγμένα αποτελέσματα, ο Λέβιν θεωρεί ότι ο φυσικός κόσμος δεν μπορεί να παράγει ουσιαστικές πληροφορίες σχετικά με μη υπολογίσιμα προβλήματα, όπως το πρόβλημα της μηχανής Τούρινγκ.[11]

Βιβλιογραφία

[Επεξεργασία | επεξεργασία κώδικα]
  • Dennis Shasha, Cathy Lazere: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists, ISBN 0-387-97992-1.

Παραπομπές

[Επεξεργασία | επεξεργασία κώδικα]
  1. ↑ (Αγγλικά) Mathematics Genealogy Project.
  2. ↑ (Αγγλικά) Guggenheim Fellows database. leonid-a-levin. Ανακτήθηκε στις 28  Απριλίου 2022.
  3. ↑ 3,0 3,1 Levin, Leonid (1986). «Average-case complete problems». SIAM J. Comput. 15 (1): 285–6. doi:10.1137/0215020. http://epubs.siam.org/doi/abs/10.1137/0215020. 
  4. ↑ 4,0 4,1 4,2 Levin's curriculum vitae
  5. ↑ 5,0 5,1 ACM press release, August 22, 2012 Αρχειοθετήθηκε March 3, 2016, στο Wayback Machine.
  6. ↑ 1971 Dissertation (in Russian); English translation at arXiv
  7. ↑ Shasha, Dennis· Cathy Lazere (Σεπτεμβρίου 1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer ScientistsΑπαιτείται δωρεάν εγγραφή. Springer. ISBN 0-387-97992-1. 
  8. ↑ Levin, Leonid (1973). «Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)». Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii) 9 (3): 115–116.  (pdf)
  9. ↑ Boris A. Trakhtenbrot (1984). «A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms». Annals of the History of Computing (IEEE) 6 (4): 384–400. doi:10.1109/MAHC.1984.10036. https://www.computer.org/csdl/mags/an/1984/04/man1984040384-abs.html. 
  10. ↑ «Peano axioms | mathematics | Britannica». www.britannica.com (στα Αγγλικά). Ανακτήθηκε στις 12 Απριλίου 2023. 
  11. ↑ «A Turing Machine Overview». aturingmachine.com. Ανακτήθηκε στις 12 Απριλίου 2023.