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

Ο Λεονίντ Ανατόλιεβιτς Λέβιν (, · γενν. 2 Νοεμβρίου 1948) είναι Σοβιετοαμερικανός μαθηματικός και επιστήμονας υπολογιστών. Είναι περισσότερο γνωστός για την ανακάλυψη της έννοιας της NP-πληρότητας παράλληλα με τον Στίβεν Κουκ και για αποτελέσματα που ενισχύουν τα θεωρήματα μη πληρότητας του Γκέντελ.

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

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

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

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

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

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

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

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

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

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

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

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

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

Βιβλιογραφία
 Dennis Shasha, Cathy Lazere: Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists, ISBN 0-387-97992-1.

Παραπομπές

Μαθηματικοί αναλυτές
Σοβιετικοί μαθηματικοί
Μαθηματικοί του 20ού αιώνα
Μαθηματικοί του 21ου αιώνα
Αμερικανοί μαθηματικοί