Φανταστείτε ότι είστε σε μια προσπάθεια να κατανοήσετε την ίδια τη φύση του υπολογισμού. Είσαι βαθιά στην ερημιά, μακριά από κανένα μονοπάτι, και ανεξιχνίαστος μηνύματα είναι σκαλισμένα στους κορμούς των δέντρων γύρω σας — BPP, AC⁰[m], Σ₂P, YACC και εκατοντάδες άλλα. Οι γλύφοι προσπαθούν να σας πουν κάτι, αλλά από πού να ξεκινήσετε; Δεν μπορείς καν να τα κρατήσεις όλα ίσια.

Λίγοι ερευνητές έχουν κάνει τόσα όσα Ράσελ Ιμπαγλιάτσο για να ξεπεράσει αυτό το φαινομενικό χάος. Για 40 χρόνια, ο Impagliazzo εργάστηκε στην πρώτη γραμμή της θεωρίας της υπολογιστικής πολυπλοκότητας, στη μελέτη της εγγενούς δυσκολίας διαφορετικών προβλημάτων. Η πιο διάσημη ανοιχτή ερώτηση σε αυτό το πεδίο, που ονομάζεται πρόβλημα P έναντι NP, ρωτά εάν πολλά φαινομενικά δύσκολα υπολογιστικά προβλήματα είναι πραγματικά εύκολα — με τον σωστό αλγόριθμο. Μια απάντηση θα είχε εκτεταμένες επιπτώσεις για την επιστήμη και την ασφάλεια της σύγχρονης κρυπτογραφίας.

Στις δεκαετίες του 1980 και του 1990, ο Impagliazzo διαδραμάτισε πρωταγωνιστικό ρόλο στην ενοποίηση των θεωρητικές βάσεις της κρυπτογραφίας. Το 1995, διατύπωσε τη σημασία αυτών των νέων εξελίξεων σε ένα εμβληματικό έγγραφο που επαναδιατύπωσε πιθανές λύσεις στο P έναντι του NP και μια χούφτα συναφών προβλημάτων στη γλώσσα του πέντε υποθετικούς κόσμους θα μπορούσαμε να κατοικούμε, που ονομάζονται ιδιότροπα Algorithmica, Heuristica, Pessiland, Minicrypt και Cryptomania. Οι πέντε κόσμοι του Impagliazzo έχουν εμπνεύσει μια γενιά ερευνητών και συνεχίζουν να καθοδηγούν την έρευνα στο ακμάζον υποπεδίο του μετα-πολυπλοκότητα.

Και αυτοί δεν είναι οι μόνοι κόσμοι που έχει ονειρευτεί. Ο Impagliazzo είναι λάτρης της ζωής των επιτραπέζιων παιχνιδιών ρόλων όπως το Dungeons and Dragons και του αρέσει να εφευρίσκει νέα σύνολα κανόνων και νέες ρυθμίσεις για εξερεύνηση. Το ίδιο παιχνιδιάρικο πνεύμα εμψυχώνει την 30χρονη πρακτική του στην αυτοσχεδιαστική κωμωδία.

Ο Impagliazzo έκανε επίσης θεμελιώδη εργασία διευκρινίζοντας τον θεμελιώδη ρόλο της τυχαιότητας στον υπολογισμό. Στα τέλη της δεκαετίας του 1970, επιστήμονες υπολογιστών ανακάλυψαν ότι η τυχαιότητα μπορεί μερικές φορές βελτίωση αλγορίθμων για την επίλυση εγγενώς ντετερμινιστικών προβλημάτων - ένα αντιφατικό εύρημα που μπερδεύει τους ερευνητές για χρόνια. Η δουλειά του Impagliazzo με τον θεωρητικό της πολυπλοκότητας Avi Wigderson και άλλοι ερευνητές στη δεκαετία του 1990 έδειξαν ότι αν ορισμένα υπολογιστικά προβλήματα είναι πραγματικά θεμελιωδώς δύσκολα, τότε είναι πάντα δυνατό για τη μετατροπή αλγορίθμων που χρησιμοποιούν τυχαιότητα σε ντετερμινιστικούς. Και αντίστροφα, αποδεικνύοντας ότι η τυχαιότητα μπορεί να εξαλειφθεί από οποιονδήποτε αλγόριθμο θα αποδείκνυε επίσης ότι υπάρχουν πραγματικά δύσκολα προβλήματα.

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

Πότε ενδιαφέρθηκες για πρώτη φορά για τα μαθηματικά;

Ενδιαφερόμουν για τα μαθηματικά πριν ακόμα καταλάβω τι ήταν. Στην τρίτη δημοτικού, οι βαθμοί μου στα μαθηματικά άρχισαν να γλιστρούν επειδή υποτίθεται ότι απομνημονεύαμε τους πίνακες πολλαπλασιασμού μας και αρνήθηκα. Η μητέρα μου είπε, «Μα Ράσελ, σου αρέσουν τα μαθηματικά, γιατί δεν το κάνεις αυτό;» Και είπα, «Αυτό δεν είναι μαθηματικά, αυτό είναι αποστήθιση. Τα πραγματικά μαθηματικά δεν περιλαμβάνουν απομνημόνευση». Το μόνο που είχα μάθει σε εκείνο το σημείο ήταν αριθμητική, οπότε δεν είμαι σίγουρος από πού βρήκα την ιδέα ότι τα μαθηματικά αφορούσαν αφηρημένες έννοιες.

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

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

Είχα σκοπό να σπουδάσω λογική. Αλλά πολλές από τις έννοιες, όταν προσπαθήσατε να τις επισημοποιήσετε πραγματικά, περιελάμβαναν υπολογισμούς και ειδικά όρια στον υπολογισμό. Ερωτήσεις όπως "Πώς γνωρίζουμε ότι τα πράγματα στα μαθηματικά είναι αληθινά;" και "Πώς καταλαβαίνουμε τη δυσκολία του να κάνουμε μαθηματικά;" οδήγησε στη θεωρητική επιστήμη των υπολογιστών και ιδιαίτερα στη θεωρία της πολυπλοκότητας.

Μερικά από τα πιο διάσημα έργα σας διερευνούν τις συνδέσεις μεταξύ κρυπτογραφίας και θεωρίας υπολογιστικής πολυπλοκότητας. Γιατί συνδέονται αυτά τα δύο πεδία;

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

Ποια είναι η διαφορά μεταξύ ενός προβλήματος και ενός παζλ;

Γενικά, το άτομο που θέτει ένα πρόβλημα μπορεί να μην γνωρίζει την απάντηση. Ένα παζλ είναι ένα πρόβλημα που έχει σχεδιαστεί με μια απάντηση στο μυαλό. Γιατί λοιπόν χρειαζόμαστε ένα παζλ; Γιατί πρέπει να είμαστε σε θέση να προσδιορίσουμε εάν ένα άτομο που υποτίθεται ότι το έλυσε το έλυσε πράγματι. Στην καθημερινή ζωή, χρησιμοποιούμε παζλ για διασκέδαση, αλλά τα χρησιμοποιούμε επίσης στις τάξεις για να ελέγξουμε αν οι άνθρωποι κατάλαβαν το υλικό. Αυτό συμβαίνει στην κρυπτογραφία: Χρησιμοποιούμε παζλ για να ελέγξουμε τις γνώσεις κάποιου.

Η διαφορά μεταξύ των πέντε κόσμων είναι πώς απαντούν στις ερωτήσεις "Υπάρχουν δύσκολα προβλήματα;" και "Υπάρχουν σκληροί γρίφοι;"

Πώς παίζονται αυτές οι διαφορετικές απαντήσεις;

Στον πρώτο κόσμο, την Algorithmica, κανένα πρόβλημα δεν είναι δύσκολο. Δεν χρειάζεται να γνωρίζετε πώς σχεδίασε κάποιος το πρόβλημά σας: Μπορείτε πάντα να το λύσετε. Η Heuristica λέει, «Λοιπόν, ίσως μερικά προβλήματα είναι δύσκολα». Μετά φτάνουμε στο Pessiland, όπου πολλά προβλήματα είναι δύσκολα, αλλά τα περισσότερα παζλ δεν είναι. Σχεδόν οποιοδήποτε πρόβλημα δημιουργώ όπου ξέρω τη λύση, θα μπορείτε να το λύσετε κι εσείς. Όλοι αυτοί οι κόσμοι είναι κακοί για την κρυπτογραφία.

Στο Minicrypt, μπορώ να δημιουργήσω γρίφους που ξέρω πώς να λύσω και που εξακολουθούν να είναι πραγματικά δύσκολοι για εσάς. Και τέλος, το Cryptomania είναι ένας κόσμος στον οποίο δύο άνθρωποι μπορούν να σταθούν σε μια δημόσια τοποθεσία όπου ένας κρυφακάς μπορεί να ακούσει και μαζί να δημιουργήσουν ένα παζλ που εξακολουθεί να είναι δύσκολο για αυτόν που κρυφακούει.

Τι σας παρακίνησε να γράψετε το χαρτί των πέντε Κόσμων;

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

Υπήρχε ένα πολύ διορατικό έγγραφο μόλις λίγα χρόνια νωρίτερα που καθόριζε τις διακρίσεις χρησιμοποιώντας πολλές αλληλένδετες ερωτήσεις με περίπου 20 πιθανές απαντήσεις. Ένας λόγος για τον οποίο ήθελα να γράψω την εφημερίδα των πέντε κόσμων ήταν ότι είχαμε κάνει τεράστια πρόοδο αυτά τα λίγα χρόνια. Θα ήταν δύσκολο να βρω ονόματα για 20 πιθανούς κόσμους.

Γιατί λοιπόν να το πλαισιώσει έτσι, ως διαφορετικοί κόσμοι με ιδιόρρυθμα ονόματα;

Είχα συμφωνήσει να γράψω αυτή την εργασία για ένα συνέδριο. Έμενα ξύπνιος αργά το βράδυ προσπαθώντας να καταλάβω τι θα έλεγα, και κάπου γύρω στη 1 π.μ. το καδράρισμα των διαφορετικών κόσμων φαινόταν καλή ιδέα. Και μετά το διάβασα το επόμενο πρωί και εξακολουθούσε να μου φαινόταν μια εντάξει ιδέα — ήταν ένας τρόπος να δείξω πώς αυτές οι ιδέες θα επηρέαζαν πραγματικά τον κόσμο χωρίς να εμπλέκονται σε ποσοτικές λεπτομέρειες. Αυτό που με κάνει πιο χαρούμενο για αυτήν την εργασία είναι ότι ακούω από ανθρώπους που κάνουν έρευνα σε θέματα πολυπλοκότητας ότι αυτή ήταν η εργασία που τους έκανε να ενδιαφέρονται για τον τομέα ως προπτυχιακοί φοιτητές.

Έχουν αποκλείσει οι ερευνητές κάποιον από τους πέντε πιθανούς κόσμους;

Στην πραγματικότητα προσθέτουμε περισσότερα — ο κόσμος έχει αρχίσει να μιλάει Obfustopia ως ένας κόσμος ακόμα ισχυρότερων κρυπτογραφικών εργαλείων. Είναι λίγο απογοητευτικό που σημειώσαμε τόση πρόοδο στα τέλη της δεκαετίας του 1980 και δεν έχουμε εξαλείψει κανέναν κόσμο από τότε. Αλλά από την άλλη, γνωρίζουμε πολλά περισσότερα για τις συνδέσεις μεταξύ των κόσμων και έχουμε α πολύ πιο ξεκάθαρη εικόνα για το πώς θα έμοιαζε κάθε κόσμος.

Οι υποθετικοί κόσμοι παίζουν επίσης έναν άλλο ρόλο στη θεωρία πολυπλοκότητας, σε αποδείξεις που υποθέτουν την ύπαρξη «χρησμών». Λοιπόν, πρώτα απ 'όλα, τι ακριβώς είναι ο χρησμός;

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

Πιστεύουν οι ερευνητές αυτά τα μαγικά κουτιά θα μπορούσαν πραγματικά να υπάρχουν;

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

Έχετε επίσης ανακαλύψει συνδέσμους μεταξύ υπολογιστικής σκληρότητας και τυχαίας. Πώς λειτουργεί αυτή η σύνδεση;

Είναι πραγματικά ένας τρόπος να πεις ότι αν δεν καταλαβαίνεις κάτι, τότε μπορεί να φαίνεται τυχαίο. Ας υποθέσουμε ότι λέω ότι σκέφτομαι έναν αριθμό μεταξύ ενός και χίλιου. Εάν διαλέξω τον αριθμό τυχαία, έχετε μία στις χίλιες πιθανότητες να τον μαντέψετε. Και αν ρωτήσω — ακολουθώντας τους Monty Python — «Σε μίλια ανά ώρα, ποια είναι η μέση ταχύτητα αέρα ενός Ευρωπαίου χελιδονιού;» έχεις περίπου την ίδια ευκαιρία. Πιθανότατα πηγαίνει περισσότερο από ένα μίλι την ώρα, και πιθανότατα δεν πηγαίνει περισσότερο από χίλια μίλια την ώρα.

Αυτό δεν είναι στην πραγματικότητα τυχαίο - είναι μια ντετερμινιστικά απαντώμενη ερώτηση. Θα μπορούσαμε απλώς να μετρήσουμε όλα τα χελιδόνια που πετούν τριγύρω, αλλά είναι κάπως δύσκολο να το προσδιορίσουμε με περιορισμένους πόρους, όπως το να μην έχουμε προϋπολογισμό για τη μέτρηση της ταχύτητας κατάποσης και να μην έχουμε άπειρη ποσότητα χελιδονιών.

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

Μιλώντας για τους Monty Python, ξέρω ότι κάνετε κωμωδία αυτοσχεδιασμού εδώ και πολύ καιρό — πώς ξεκινήσατε;

Ξεκίνησα ως επίκουρος καθηγητής στο Σαν Ντιέγκο το 1991. Και γύρω στο '94 περίπου, σκέφτηκα, «Πραγματικά δεν έχω πολλή ζωή έξω από το τμήμα». Πήρα λοιπόν τη δωρεάν εβδομαδιαία εφημερίδα και κοίταξα τη λίστα με τις λέσχες και τις δραστηριότητες. Εξάλειψα τα πάντα εκτός από την κωμωδία αυτοσχεδιασμού — σκέφτηκα ότι ήταν τουλάχιστον εύλογο ότι θα ήμουν εντάξει σε αυτό. Γνώρισα τη γυναίκα μου σε εκείνη την τάξη αρχαρίων.

Τι σκέφτηκε;

Λέει ότι ήμουν πραγματικά απαίσια. Όταν είσαι λογικός, είσαι εκπαιδευμένος να σκέφτεσαι πάντα την απόχρωση κάθε λέξης. Δεν θέλεις να πεις κάτι λάθος. Το Improv είναι υπέροχο στο ότι αντιστρέφει αυτό: Το θέμα δεν είναι να πεις κάτι τέλειο, αλλά να φτιάξεις κάτι γρήγορα. Ήταν το αντίθετο από την υπόλοιπη ζωή μου.

Η πλέον γυναίκα μου έκανε ένα διάλειμμα από το μάθημα και όταν επέστρεψε ένα χρόνο αργότερα, κατάφερα να την εντυπωσιάσω. Αυτό ήταν πριν από 30 χρόνια. Παρακολουθώ ακόμα το ίδιο μάθημα με τον ίδιο δάσκαλο.

Το να κάνετε βελτιώσεις έχει αλλάξει τον τρόπο που προσεγγίζετε την έρευνά σας;

Είναι καλή πρακτική να μην είστε υπερκριτικοί για κάθε σκέψη που κάνετε. Αυτό είναι ιδιαίτερα χρήσιμο στις συνεργασίες. Όταν δούλευα με άλλους ανθρώπους, συνήθιζα να λέω πράγματα όπως, «Αλλά αυτή η ιδέα δεν θα λειτουργήσει για τον ακόλουθο λόγο. Αυτό δεν είναι κυριολεκτικά αλήθεια.” Στον αυτοσχεδιασμό, πρέπει πάντα να αποδέχεσαι αυτά που λέει ο σύντροφός σου. Και νομίζω ότι αυτή είναι μια καλή στάση, ειδικά όταν κάνετε έρευνα με μαθητές: Μην απορρίπτετε κάτι που λένε μόνο και μόνο επειδή ξέρετε ότι είναι λάθος. Υπάρχουν πολλές καλές ιδέες που δεν είναι 100% σωστές.

Σαν τι?

Όταν προσπαθείτε να αποκτήσετε διαίσθηση για ένα πρόβλημα, ένα πράγμα που βοηθάει είναι να ξεκινήσετε με μερικές απλοποιητικές υποθέσεις. Αυτές οι υποθέσεις συνήθως δεν είναι αληθινές, αλλά μπορούν να σας βοηθήσουν να καταλήξετε σε έναν οδικό χάρτη. Πες, «Αν είχα έναν ελέφαντα, θα μπορούσα να ξεπεράσω τα βουνά. Φυσικά, δεν έχω ελέφαντα. Αλλά αν το έκανα, ορίστε πώς θα το έκανα». Και τότε συνειδητοποιείς, «Λοιπόν, ίσως δεν χρειάζομαι έναν ελέφαντα για αυτό το βήμα. Ένα μουλάρι θα ήταν μια χαρά».

Τι γίνεται με την αγάπη σας για τα παιχνίδια ρόλων — αυτό έχει επηρεάσει καθόλου τη δουλειά σας;

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

Γιατί τα παιχνίδια ρόλων είναι τόσο συναρπαστικός τρόπος για να εξερευνήσετε υποθετικούς κόσμους;

Οι άνθρωποι που ασχολούνται με τη κερδοσκοπική φαντασία ανέκαθεν εφευρίσκουν κόσμους. Ο Tolkien είναι πιο διάσημος γι' αυτό και είχε τόσο τεράστια φαντασία που πραγματικά ένιωθε να ζει ο κόσμος του. είναι ένας τρόπος να γίνει αυτό. Τώρα δεν είναι μόνο ο κόσμος μου. Μπορεί να ξεκίνησε όπως το φανταζόμουν, αλλά όπως σε κάθε συνεργασία, λόγω της συνεισφοράς όλων των άλλων έχει εξελιχθεί πολύ πέρα ​​από αυτό.