Η Avi Wigderson, πρωτοπόρος της θεωρίας πολυπλοκότητας, κερδίζει το βραβείο Turing | Περιοδικό Quanta

Για περισσότερα από 40 χρόνια, η Avi Wigderson μελετά προβλήματα. Αλλά ως θεωρητικός της υπολογιστικής πολυπλοκότητας, δεν ενδιαφέρεται απαραίτητα για τις απαντήσεις σε αυτά τα προβλήματα. Συχνά θέλει απλώς να μάθει αν είναι επιλύσιμα ή όχι και πώς να τα πει. «Η κατάσταση είναι γελοία», είπε Wigderson, επιστήμονας υπολογιστών στο Ινστιτούτο Προηγμένων Μελετών στο Πρίνστον του Νιου Τζέρσεϊ. Ανεξάρτητα από το πόσο δύσκολη φαίνεται μια ερώτηση, ένας αποτελεσματικός τρόπος απάντησης θα μπορούσε να είναι η απόκρυψη που δεν είναι εφικτή. «Από όσο γνωρίζουμε, για κάθε πρόβλημα που αντιμετωπίζουμε και προσπαθούμε να λύσουμε, δεν μπορούμε να αποκλείσουμε ότι έχει έναν αλγόριθμο που μπορεί να το λύσει. Αυτό είναι το πιο ενδιαφέρον πρόβλημα για μένα».

Σήμερα ο Wigderson αναδείχθηκε νικητής του Βραβείο AM Turing, που θεωρείται ευρέως μία από τις κορυφαίες διακρίσεις στην επιστήμη των υπολογιστών, για τη θεμελιώδη συνεισφορά του στη θεωρία των υπολογισμών. Το έργο του Wigderson έχει αγγίξει σχεδόν κάθε τομέα του γηπέδου. Οι συνάδελφοί του, οι συνεργάτες και οι καθοδηγητές του λένε ότι βρίσκει συνεχώς απροσδόκητες γέφυρες μεταξύ διαφορετικών περιοχών. Και η εργασία του για την τυχαιότητα και τους υπολογισμούς, ξεκινώντας από τη δεκαετία του 1990, αποκάλυψε βαθιές συνδέσεις μεταξύ των μαθηματικών και της επιστήμης των υπολογιστών που αποτελούν τη βάση των σημερινών ερευνών.

Madhu Sudan, ένας επιστήμονας υπολογιστών στο Πανεπιστήμιο του Χάρβαρντ που κέρδισε το βραβείο Rolf Nevanlinna το 2002 (τώρα ονομάζεται Βραβείο Abacus), είπε ότι η επιρροή του Wigderson στο πεδίο είναι αδύνατο να χαθεί. «Είναι πολύ δύσκολο να εργαστείς σε οποιοδήποτε χώρο στην επιστήμη των υπολογιστών χωρίς να διασταυρωθείς με το έργο του Avi», είπε ο Σουδάν. «Και παντού, βρίσκεις πολύ βαθιές γνώσεις». Στα τέλη της δεκαετίας του 1980, για παράδειγμα, ο Σουδάν εργάστηκε με τον Wigderson σε ένα χαρτί που ερευνούσε τις συνδέσεις μεταξύ ορισμένων μαθηματικών συναρτήσεων και πολυωνύμων. Αυτό το έργο ξεκίνησε ολόκληρη την καριέρα του Σουδάν. «Αυτό είναι χαρακτηριστικό για τον Άβι», είπε ο Σουδάν. «Μπαίνει σε κάποιο χώρο, κάνει τις σωστές ερωτήσεις και μετά προχωρά».

Ο Wigderson μεγάλωσε στη Χάιφα του Ισραήλ, ως ένας από τους τρεις γιους μιας νοσοκόμας και ενός ηλεκτρολόγου μηχανικού, και οι δύο επιζήσαντες του Ολοκαυτώματος. Ο πατέρας του αγαπούσε τα παζλ και ενδιαφερόταν έντονα για τις θεμελιώδεις ιδέες στα μαθηματικά, τις οποίες μοιραζόταν με τα παιδιά του. «Είναι ο τύπος από τον οποίο μολύνθηκα από αυτόν τον ιό», είπε ο Wigderson. Όταν ξεκίνησε το κολέγιο τη δεκαετία του 1970, στο Technion στη Χάιφα, ήθελε να σπουδάσει μαθηματικά, αλλά οι γονείς του τον οδήγησαν στην επιστήμη των υπολογιστών. «Σκέφτηκαν ότι ίσως ήταν καλή ιδέα ότι θα είχα δουλειά όταν τελειώσω», είπε.

Βρήκε ένα χωράφι πλούσιο με βαθιά, αναπάντητα ερωτήματα που ήταν μαθηματικά στην καρδιά. Μια από τις πρώτες πρωτοποριακές προσπάθειές του επικεντρώθηκε σε μια φαινομενική αντίφαση: αν ήταν δυνατό να πείσει κάποιον άλλο ότι μια μαθηματική δήλωση είχε αποδειχθεί χωρίς να δείξει πώς.

«Το άτομο που βλέπει την απόδειξη δεν μαθαίνει τίποτα για την ίδια την απόδειξη», είπε Ραν Ραζ, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Πρίνστον. Το 1985, οι Shafi Goldwasser, Silvio Micali και Charles Rackoff εισήγαγαν αυτή την έννοια διαδραστικές αποδείξεις μηδενικής γνώσης, επιδεικνύοντας τη χρήση του για μερικές δηλώσεις. Ο Wigderson, μαζί με τους Micali και Oded Goldreich, εξέθεσαν αργότερα αυτήν την ιδέα, θέτοντας τις προϋποθέσεις που δείχνουν ότι εάν μια δήλωση μπορεί να αποδειχθεί, έχει επίσης απόδειξη μηδενικής γνώσης.

«Αυτό είναι ένα βασικό αποτέλεσμα στην κρυπτογραφία. είναι εξαιρετικά κεντρικό», είπε ο Raz. Χρησιμοποιώντας μια απόδειξη μηδενικής γνώσης, κάποιος μπορεί να αποδείξει ότι κρυπτογραφήθηκε σωστά ή υπέγραψε ένα μήνυμα χρησιμοποιώντας το μυστικό κλειδί του, χωρίς να αποκαλύψει καμία πληροφορία σχετικά με αυτό. "Το Avi έχει μερικά εξαιρετικά σημαντικά αποτελέσματα στην κρυπτογραφία, και αυτό μπορεί να είναι το πιο σημαντικό από αυτά."

Αλλά ίσως το πιο θεμελιώδες αποτέλεσμα του Wigderson βρίσκεται σε έναν άλλο τομέα: τη σύνδεση της υπολογιστικής σκληρότητας με τυχαία. Στα τέλη της δεκαετίας του 1970, οι επιστήμονες υπολογιστών είχαν συνειδητοποιήσει ότι για πολλά δύσκολα προβλήματα, οι αλγόριθμοι που χρησιμοποιούσαν την τυχαιότητα, που ονομάζονται επίσης πιθανολογικοί αλγόριθμοι, μπορούσαν να υπερβούν κατά πολύ τις ντετερμινιστικές εναλλακτικές τους. Σε ένα Απόδειξη 1977, για παράδειγμα, ο Robert Solovay και ο Volker Strassen εισήγαγαν έναν τυχαιοποιημένο αλγόριθμο που θα μπορούσε να καθορίσει εάν ένας αριθμός είναι πρώτος ταχύτερος από τους καλύτερους ντετερμινιστικούς αλγόριθμους εκείνης της εποχής.

Για ορισμένα προβλήματα, οι πιθανολογικοί αλγόριθμοι μπορούν να δείχνουν ντετερμινιστικούς. Στις αρχές της δεκαετίας του 1980, ο Wigderson εργάστηκε με τον Richard Karp του Πανεπιστημίου της Καλιφόρνια στο Μπέρκλεϋ, για να συνδέσει την ιδέα της τυχαιότητας με προβλήματα που θεωρούνται υπολογιστικά δύσκολα, πράγμα που σημαίνει ότι κανένας γνωστός ντετερμινιστικός αλγόριθμος δεν μπορεί να τα λύσει σε εύλογο χρονικό διάστημα. «Δεν ξέρουμε πώς να αποδείξουμε ότι είναι σκληροί», είπε ο Wigderson. Ωστόσο, αυτός και ο Karp βρήκαν έναν τυχαιοποιημένο αλγόριθμο για ένα συγκεκριμένο δύσκολο πρόβλημα που αργότερα μπόρεσαν να αποτυχαιοποιήσουν, αποκαλύπτοντας αποτελεσματικά έναν ντετερμινιστικό αλγόριθμο για αυτό. Την ίδια περίοδο, άλλοι ερευνητές έδειξαν πώς οι υποθέσεις υπολογιστικής σκληρότητας σε προβλήματα κρυπτογραφίας θα μπορούσαν να επιτρέψουν την αποτυχαιοποίηση γενικά.

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

Για ένα χαρτί 1994, αυτός και ο επιστήμονας υπολογιστών Noam Nisan φώτισαν αυτή τη σύνδεση. Απέδειξαν ότι εάν υπάρχουν φυσικά σκληρά προβλήματα, όπως υποψιάζονται οι περισσότεροι επιστήμονες υπολογιστών, τότε κάθε αποτελεσματικός τυχαιοποιημένος αλγόριθμος μπορεί να αντικατασταθεί από έναν αποτελεσματικό ντετερμινιστικό. «Μπορείς πάντα να εξαλείψεις την τυχαιότητα», είπε ο Wigderson.

Είναι σημαντικό ότι ανακάλυψαν ότι οι ντετερμινιστικοί αλγόριθμοι μπορεί να χρησιμοποιούν «ψευδοτυχαίες» ακολουθίες - σειρές δεδομένων που εμφανίζονται τυχαίες αλλά δεν είναι. Έδειξαν επίσης πώς μπορούν να χρησιμοποιηθούν οποιαδήποτε δύσκολα προβλήματα για την κατασκευή μιας γεννήτριας ψευδοτυχαίων. Η τροφοδοσία των ψευδοτυχαίων bits (αντί των τυχαίων) σε έναν αλγόριθμο πιθανοτήτων θα έχει ως αποτέλεσμα έναν αποτελεσματικό ντετερμινιστικό για το ίδιο πρόβλημα.

Το Σουδάν είπε ότι το χαρτί βοήθησε τους επιστήμονες υπολογιστών να αναγνωρίσουν βαθμούς τυχαιότητας που θα μπορούσαν να βοηθήσουν στην αποκάλυψη των περιπλοκών των δύσκολων προβλημάτων και στον τρόπο επίλυσής τους. «Δεν είναι μόνο η τυχαιότητα, αλλά οι αντιλήψεις της τυχαιότητας», είπε. «Αυτό είναι το κλειδί».

Το Σουδάν επισημαίνει ότι η τυχαιότητα φαίνεται να εμφανίζεται παντού, αλλά στην πραγματικότητα είναι εξαιρετικά δύσκολο να βρεθεί. «Οι άνθρωποι σας λένε ότι τα ψηφία του pi φαίνονται τυχαία ή η ακολουθία των αριθμών που είναι πρώτοι φαίνεται τυχαία», είπε. «Είναι απόλυτα αποφασισμένοι, αλλά μας φαίνονται τυχαίοι». Η αντίληψη της τυχαιότητας, είπε, βρίσκεται στην καρδιά της επιστήμης των υπολογιστών σήμερα. «Και αυτό είναι κάτι που ο Avi έχει προωθήσει πάρα πολύ».

Η τυχαιότητα έχει γίνει ένας ισχυρός πόρος στη θεωρία πολυπλοκότητας, αλλά είναι άπιαστος. Οι ανατροπές κερμάτων και οι ρίψεις ζαριών, επισημαίνει ο Wigderson, δεν είναι πραγματικά τυχαίες: Εάν έχετε αρκετές πληροφορίες για το φυσικό σύστημα, τότε το αποτέλεσμα είναι απολύτως προβλέψιμο. Η τέλεια τυχαιότητα, είπε, είναι άπιαστη και δύσκολο να επαληθευτεί.

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