Το 50-ετές ταξίδι της θεωρίας πολυπλοκότητας στα όρια της γνώσης | Περιοδικό Quanta

Την πρώτη εβδομάδα του φθινοπωρινού εξαμήνου του 2007, ο Marco Carmosino σύρθηκε σε ένα μάθημα μαθηματικών που απαιτείται για όλες τις ειδικότητες της επιστήμης των υπολογιστών στο Πανεπιστήμιο της Μασαχουσέτης, στο Amherst. Ο Carmosino, δευτεροετής φοιτητής, σκεφτόταν να εγκαταλείψει το κολέγιο για να σχεδιάσει βιντεοπαιχνίδια. Τότε ο καθηγητής έθεσε μια απλή ερώτηση που θα άλλαζε την πορεία της ζωής του: Πώς ξέρετε ότι τα μαθηματικά λειτουργούν στην πραγματικότητα;

«Αυτό με έκανε να καθίσω και να δώσω προσοχή», θυμάται Carmosino, τώρα θεωρητικός επιστήμονας υπολογιστών στην IBM. Εγγράφηκε σε ένα προαιρετικό σεμινάριο για το έργο του Kurt Gödel, του οποίου τα ιλιγγιώδη αυτοαναφορικά επιχειρήματα εξέθεσαν πρώτα τα όρια του μαθηματικού συλλογισμού και δημιούργησαν τη βάση για κάθε μελλοντική εργασία σχετικά με τα θεμελιώδη όρια του υπολογισμού. Ήταν πολλά να δεχτώ.

«Δεν κατάλαβα 100%», είπε ο Carmosino. «Αλλά ήξερα ότι το ήθελα».

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

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

«Δεν υπάρχει οδικός χάρτης», είπε Μάικλ Σίπσερ, ένας βετεράνος θεωρητικός της πολυπλοκότητας στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης που πέρασε χρόνια αντιμετωπίζοντας το πρόβλημα τη δεκαετία του 1980. «Είναι σαν να πηγαίνεις στην έρημο».

Φαίνεται ότι η απόδειξη ότι τα υπολογιστικά προβλήματα είναι δύσκολο να επιλυθούν είναι από μόνη της μια δύσκολη υπόθεση. Αλλά γιατί είναι τόσο δύσκολο; Και πόσο δύσκολο είναι; Ο Carmosino και άλλοι ερευνητές στο υποπεδίο της μετα-πολυπλοκότητας επαναδιατυπώνουν ερωτήματα σαν αυτό ως υπολογιστικά προβλήματα, προωθώντας το πεδίο προς τα εμπρός στρέφοντας τον φακό της θεωρίας πολυπλοκότητας πίσω στον εαυτό του.

«Μπορεί να σκεφτείτε, «Εντάξει, αυτό είναι κάπως ωραίο. Ίσως οι θεωρητικοί της πολυπλοκότητας να έχουν τρελαθεί», είπε Ραχούλ Ιλάνγκο, μεταπτυχιακός φοιτητής στο MIT που έχει παράγει μερικά από τα πιο συναρπαστικά πρόσφατα αποτελέσματα στον τομέα.

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

«Έχει γίνει σαφές ότι η μετα-πολυπλοκότητα είναι κοντά στην καρδιά των πραγμάτων», είπε Σκοτ Άαρσον, θεωρητικός της πολυπλοκότητας στο Πανεπιστήμιο του Τέξας στο Ώστιν.

Αυτή είναι η ιστορία του μακρού και στριφογυριστού μονοπατιού που οδήγησε τους ερευνητές από το πρόβλημα P έναντι NP στη μετα-πολυπλοκότητα. Δεν ήταν ένα εύκολο ταξίδι - το μονοπάτι είναι γεμάτο με ψεύτικες στροφές και οδοφράγματα, και επανέρχεται ξανά και ξανά. Ωστόσο, για τους ερευνητές της μετα-πολυπλοκότητας, αυτό το ταξίδι σε ένα αχαρτογράφητο τοπίο είναι η δική του ανταμοιβή. Αρχίστε να κάνετε φαινομενικά απλές ερωτήσεις, είπε Valentine Kabanets, θεωρητικός της πολυπλοκότητας στο Πανεπιστήμιο Simon Fraser στον Καναδά, και «δεν έχετε ιδέα πού θα πάτε».

Γνωστοί Άγνωστοι

Το πρόβλημα P εναντίον NP οφείλει το αθώο όνομά του στη συνήθεια των θεωρητικών της πολυπλοκότητας να ταξινομούν τα υπολογιστικά προβλήματα σε ευρεία «τάξεις πολυπλοκότητας” με ετικέτες που υποδηλώνουν σύμβολα Nasdaq. Ένα υπολογιστικό πρόβλημα είναι αυτό που καταρχήν μπορεί να λυθεί με έναν αλγόριθμο — μια επακριβώς καθορισμένη λίστα εντολών. Αλλά δεν είναι όλοι οι αλγόριθμοι εξίσου χρήσιμοι και η διαφοροποίηση μεταξύ των αλγορίθμων υποδηλώνει θεμελιώδεις διαφορές μεταξύ προβλημάτων σε διαφορετικές κλάσεις. Η πρόκληση για τους θεωρητικούς της πολυπλοκότητας είναι να μετατρέψουν αυτές τις υποδείξεις σε αυστηρά θεωρήματα σχετικά με τις σχέσεις μεταξύ των τάξεων πολυπλοκότητας.

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

Το «P» και το «NP» είναι τα δύο πιο διάσημα μέλη του a αναπτυσσόμενο θηριοτροφείο εκατοντάδων τάξεων πολυπλοκότητας. Σε γενικές γραμμές, το P είναι η κατηγορία των προβλημάτων που μπορούν να λυθούν εύκολα, όπως η αλφαβητοποίηση μιας λίστας. Το NP είναι η κατηγορία προβλημάτων με εύκολα ελεγχόμενες λύσεις, όπως παζλ sudoku. Δεδομένου ότι όλα τα εύκολα επιλύσιμα προβλήματα είναι επίσης εύκολο να ελεγχθούν, τα προβλήματα στο P είναι επίσης σε NP. Αλλά ορισμένα προβλήματα NP φαίνονται δύσκολο να λυθούν - δεν μπορείτε να βρείτε αμέσως τη λύση σε ένα παζλ sudoku χωρίς να δοκιμάσετε πρώτα πολλές δυνατότητες. Μήπως αυτή η φαινομενική σκληρότητα είναι απλώς μια ψευδαίσθηση — ότι υπάρχει ένα απλό κόλπο για την επίλυση κάθε εύκολα ελεγχόμενου προβλήματος;

Αν ναι, τότε P = NP: Οι δύο κλάσεις είναι ισοδύναμες. Αν συμβαίνει αυτό, πρέπει να υπάρχει κάποιος αλγόριθμος που να καθιστά ασήμαντη την επίλυση τεράστιων γρίφων sudoku, τη βελτιστοποίηση των παγκόσμιων δρομολογίων αποστολής, τη διακοπή της κρυπτογράφησης αιχμής και την αυτοματοποίηση των αποδείξεων των μαθηματικών θεωρημάτων. Εάν P ≠ NP, τότε πολλά υπολογιστικά προβλήματα που είναι επιλύσιμα κατ' αρχήν θα παραμείνουν στην πράξη για πάντα πέρα ​​από την αντίληψή μας.

Οι ερευνητές ανησυχούσαν για τα όρια του επίσημου μαθηματικού συλλογισμού πολύ πριν αρθρωθεί για πρώτη φορά το πρόβλημα P έναντι NP — μάλιστα, πολύ πριν από την έναρξη της σύγχρονης επιστήμης των υπολογιστών. Το 1921, παλεύοντας με το ίδιο ερώτημα που θα τραβούσε την προσοχή του Carmosino σχεδόν έναν αιώνα αργότερα, ο μαθηματικός David Hilbert πρότεινε ένα ερευνητικό πρόγραμμα για τη γείωση των μαθηματικών με απόλυτη βεβαιότητα. Ήλπιζε να ξεκινήσει από μερικές απλές υποθέσεις, που ονομάζονται αξιώματα, και να αντλήσει μια ενοποιημένη μαθηματική θεωρία που πληρούσε τρία βασικά κριτήρια.

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

Μόλις ένα χρόνο αργότερα, ο Gödel έδωσε το πρώτο χτύπημα στο όνειρο του Hilbert. Αυτός αποδείχθηκε ότι μια αυτοκαταστροφική δήλωση όπως «αυτή η δήλωση είναι αναπόδεικτη» θα μπορούσε να προέλθει από οποιοδήποτε κατάλληλο σύνολο αξιωμάτων. Εάν μια τέτοια δήλωση είναι πράγματι μη αποδείξιμη, η θεωρία είναι ελλιπής, αλλά αν είναι αποδεδειγμένη, η θεωρία είναι ασυνεπής - ένα ακόμη χειρότερο αποτέλεσμα. Στην ίδια εργασία, ο Gödel απέδειξε επίσης ότι καμία μαθηματική θεωρία δεν θα μπορούσε ποτέ να αποδείξει τη δική της συνέπεια.

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

Στη συνέχεια, το 1936, ένας 23χρονος μεταπτυχιακός φοιτητής ονόματι Άλαν Τούρινγκ αναδιατύπωσε την συνθήκη αποφασιστικότητας του Χίλμπερτ στην άγνωστη τότε γλώσσα υπολογισμού και της έδωσε ένα θανατηφόρο πλήγμα. Ο Τούρινγκ διατύπωσε ένα μαθηματικό μοντέλο — τώρα γνωστό ως το Μηχανή Turing — που θα μπορούσε να αντιπροσωπεύει όλους τους πιθανούς αλγόριθμους και έδειξε ότι αν υπήρχε η διαδικασία του Hilbert, θα ταίριαζε σε αυτό το μοντέλο. Στη συνέχεια χρησιμοποίησε αυτοαναφορικές μεθόδους όπως του Gödel αποδειχθούν την ύπαρξη αδιευκρίνιστων δηλώσεων — ή, ισοδύναμα, μη υπολογίσιμων προβλημάτων που κανένας αλγόριθμος δεν θα μπορούσε να λύσει.

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

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

«Αναδύεται μια πλούσια θεωρία και δεν γνωρίζουμε πια τις απαντήσεις», είπε ο Carmosino.

Διαφορετικές διαδρομές

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

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

Υπάρχουν πιο εξελιγμένοι αλγόριθμοι Hamiltonian μονοπατιών που δίνουν καλύτερη μάχη, αλλά ο χρόνος που απαιτούν οι αλγόριθμοι για την επίλυση του προβλήματος αυξάνεται συνεχώς με το μέγεθος του γραφήματος. Τα γραφήματα δεν χρειάζεται να είναι πολύ μεγάλα πριν ακόμη και οι καλύτεροι αλγόριθμοι που έχουν ανακαλύψει οι ερευνητές δεν μπορούν να βρουν μια διαδρομή «σε οποιοδήποτε εύλογο χρονικό διάστημα», είπε. Ράσελ Ιμπαγλιάτσο, θεωρητικός της πολυπλοκότητας στο Πανεπιστήμιο της Καλιφόρνια στο Σαν Ντιέγκο. «Και με τον όρο «εύλογο χρονικό διάστημα», εννοώ «πριν τελειώσει το σύμπαν».

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

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

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

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

Τόσο το πρόβλημα της διαδρομής Hamiltonian όσο και το πρόβλημα της διαδρομής Eulerian ανήκουν στην κατηγορία πολυπλοκότητας NP, που ορίζεται να περιλαμβάνει όλα τα προβλήματα των οποίων οι λύσεις μπορούν να ελεγχθούν με πολυωνυμικούς αλγόριθμους. Το πρόβλημα της διαδρομής Eulerian εμπίπτει επίσης στην κλάση P επειδή ένας πολυωνυμικός αλγόριθμος μπορεί να το λύσει, αλλά απ' ό,τι φαίνεται, αυτό δεν ισχύει για το πρόβλημα της διαδρομής Hamiltoni. Γιατί αυτά τα δύο προβλήματα γραφημάτων, τόσο επιφανειακά παρόμοια, να διαφέρουν τόσο δραματικά; Αυτή είναι η ουσία του προβλήματος P έναντι NP.

Καθολικά σκληρό

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

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

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

Την ίδια περίπου εποχή, ένας μεταπτυχιακός φοιτητής στη Σοβιετική Ένωση ονομάστηκε Λεονίντ Λέβιν απέδειξε α παρόμοιο αποτέλεσμα, εκτός από το ότι εντόπισε πολλά διαφορετικά καθολικά προβλήματα. Επιπλέον, ο Αμερικανός θεωρητικός της πολυπλοκότητας Ρίτσαρντ Καρπ αποδείχθηκε ότι η ιδιότητα της καθολικότητας που εντόπισε ο Κουκ (και ο Λέβιν, αν και ο Καρπ και ο Κουκ δεν γνώριζαν το έργο του Λέβιν παρά μόνο χρόνια αργότερα) ήταν η ίδια καθολική. Σχεδόν κάθε πρόβλημα NP χωρίς γνωστό πολυωνυμικό αλγόριθμο - δηλαδή σχεδόν κάθε εύκολα ελεγχόμενο πρόβλημα που φαινόταν δύσκολο - είχε την ίδια ιδιότητα, η οποία έγινε γνωστή ως NP-πληρότητα.

Αυτό σημαίνει όλα τα προβλήματα NP-πλήρης — το πρόβλημα της διαδρομής Hamiltonian, το sudoku και χιλιάδες των άλλων — είναι κατά την ακριβή έννοια ισοδύναμα. "Έχετε όλες αυτές τις διαφορετικές φυσικές εργασίες και όλες ως δια μαγείας αποδεικνύονται το ίδιο έργο", είπε ο Ilango. «Και ακόμα δεν ξέρουμε αν αυτό το ίδιο έργο είναι δυνατό ή όχι».

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

Ο Κουκ, ο Λέβιν και ο Καρπ είχαν ενοποιήσει αυτό που φαινόταν σαν πολλά άσχετα προβλήματα. Τώρα το μόνο που έπρεπε να κάνουν οι θεωρητικοί της πολυπλοκότητας ήταν να λύσουν ένα πρόβλημα: Είναι το P = NP ή όχι;

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

Ας υποθέσουμε ότι P = NP. Για να το αποδείξουν, οι ερευνητές θα πρέπει να βρουν έναν γρήγορο αλγόριθμο για ένα πλήρες πρόβλημα NP, το οποίο μπορεί να κρύβεται σε κάποια σκοτεινή γωνιά αυτού του τεράστιου τοπίου. Δεν υπάρχει καμία εγγύηση ότι θα το βρουν σύντομα: Οι θεωρητικοί της πολυπλοκότητας έχουν κατά καιρούς ανακάλυψαν έξυπνοι αλγόριθμοι για φαινομενικά δύσκολα (αν και όχι ολοκληρωμένα NP) προβλήματα μόνο μετά από δεκαετίες εργασίας.

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

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

Μέχρι το τελευταίο έτος του Carmosino στο κολέγιο, η περιέργειά του τον είχε οδηγήσει από τον Gödel σε ένα μεταπτυχιακό μάθημα στη θεωρία της πολυπλοκότητας. Με έκπληξη συνειδητοποίησε ότι ξόδευε περισσότερο χρόνο στην εργασία του παρά στο έργο του πάθους του, ένα πρόγραμμα υπολογιστή που θα μάθαινε την αφηγηματική δομή των παραμυθιών και θα δημιουργούσε νέα.

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

«Έλεγε: «Ξέρεις, αν θέλεις να συνεχίσεις να το κάνεις αυτό, αν θέλεις να συνεχίσεις να κάνεις θεωρητική επιστήμη των υπολογιστών και θεωρία πολυπλοκότητας, μπορείς: Λέγεται μεταπτυχιακό», είπε ο Carmosino. Αφού πήρε το μεταπτυχιακό του, μετακόμισε στο Σαν Ντιέγκο το 2012 για να εργαστεί για ένα διδακτορικό υπό την επίβλεψη του Impagliazzo.

Ο κύριος στόχος του Carmosino, αρχικά, ήταν να κατανοήσει καλύτερα τον α χαρτί ορόσημο από δύο δεκαετίες νωρίτερα που είχε αιχμαλωτίσει τη φαντασία του. Αυτό το έγγραφο, από τους θεωρητικούς της πολυπλοκότητας Αλεξάντερ Ραζμπόροφ και Στίβεν Ρούντιτς, είχε δείξει ότι μια ορισμένη «φυσική» στρατηγική για την απόδειξη του P ≠ NP θα αποτύγχανε σχεδόν σίγουρα, επειδή η επιτυχία θα είχε ένα μεγάλο κόστος - την πλήρη κατάρρευση της κρυπτογραφίας - που οι ερευνητές θεωρούσαν πολύ απίθανο. Οι ερευνητές ερμήνευσαν το αποτέλεσμα του Razborov και του Rudich ως εμπόδιο σε αυτή τη δημοφιλή προσέγγιση για την απόδειξη του P ≠ NP.

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

«Η θεωρία της πολυπλοκότητας είναι καταραμένη και ευλογημένη με τόσα πολλά εμπόδια», είπε ο Ιλάνγκο.

Όταν ο Carmosino συνάντησε το φράγμα των φυσικών αποδείξεων, ήταν σχεδόν 20 ετών. Αλλά υποψιαζόταν ότι είχε περισσότερα μαθήματα για τους ερευνητές. Αυτό το συναίσθημα θα δικαιωνόταν μια μέρα όταν αυτός και τρεις συνάδελφοί του απέδειξαν ένα εκπληκτικό αποτέλεσμα εξετάζοντας το φράγμα των φυσικών αποδείξεων από την άποψη της μετα-πολυπλοκότητας. Η απόδειξή τους ήταν ένα από τα λίγα σημαντικά αποτελέσματα που πυροδότησε ένα νέο ενδιαφέρον για τη μετα-πολυπλοκότητα, οδηγώντας σε μια αναταραχή προόδου τα τελευταία αρκετά χρόνια.

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

Μια κυκλική διαδρομή

Αρχικά, οι ερευνητές προσπάθησαν να αποδείξουν P ≠ NP — δηλαδή, να αποδείξουν ότι ορισμένα προβλήματα NP δεν είναι επιλύσιμα με οποιονδήποτε πιθανό πολυωνυμικό αλγόριθμο — χρησιμοποιώντας παραλλαγές στις τεχνικές που είχε χρησιμοποιήσει ο Turing για να αποδείξει ότι ορισμένα προβλήματα δεν επιλύονται με κανέναν αλγόριθμο . Γρήγορα όμως ανακάλυψαν μια απόδειξη ότι αυτές οι μέθοδοι δεν θα λειτουργούσαν - το πρώτο σημαντικό εμπόδιο για την επίλυση του ζητήματος P έναντι NP. Άρχισαν λοιπόν να αναζητούν μια άλλη προσέγγιση και σύντομα βρήκαν μια στο έργο του σύγχρονου του Turing Κλοντ Σάνον.

Η Shannon, η οποία μεγάλωσε σε μια μικρή πόλη στο βόρειο Μίσιγκαν, φαινόταν απίθανη φιγούρα για την έναρξη της εποχής της πληροφορίας. Ωστόσο, έδωσε παράδειγμα για τη διεπιστημονική φύση του αναδυόμενου κλάδου της επιστήμης των υπολογιστών, νιώθοντας εξίσου οικεία στην ηλεκτρολογική μηχανική και τη μαθηματική λογική. Στο δικό του μεταπτυχιακή εργασία, ο Shannon έδειξε πώς κυκλώματα κατασκευασμένα από ηλεκτρομηχανικούς διακόπτες θα μπορούσαν να αντιπροσωπεύουν λογικές εκφράσεις που περιλαμβάνουν μεταβλητές Boolean - ποσότητες που μπορούν να λάβουν μόνο δύο τιμές (όπως true ή false, ή 1 και 0).

Σε αυτές τις εκφράσεις, οι μεταβλητές Boole συνδέονται μεταξύ τους με τις «λογικές πύλες» AND, OR και NOT. Η στοιχειώδης έκφραση Α ΚΑΙ Β, για παράδειγμα, είναι αληθής όταν και το Α και το Β είναι αληθές και λανθασμένα διαφορετικά. Το Α Ή Β, από την άλλη πλευρά, είναι αληθές εάν τουλάχιστον μία από τις δύο μεταβλητές είναι αληθής. Μια πύλη NOT είναι ακόμα πιο απλή: Αντιστρέφει την τιμή μιας μεμονωμένης μεταβλητής. Με αρκετά από αυτά τα βασικά δομικά στοιχεία, μπορείτε να εκτελέσετε οποιονδήποτε υπολογισμό.

«Όταν κοιτάς τον υπολογιστή σου, στο τέλος της ημέρας, τι κάνει; Κάνει σιρκουί», είπε ο Ιλάνγκο.

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

Το πλαίσιο πολυπλοκότητας κυκλώματος απαιτεί επανεξέταση των πιο βασικών εννοιών στο υπολογιστικό μοντέλο του Turing. Εδώ, αντί για υπολογιστικά προβλήματα και τους αλγόριθμους που τα λύνουν, οι ερευνητές εξετάζουν τις συναρτήσεις Boole και τα κυκλώματα που τις υπολογίζουν. Μια συνάρτηση Boole παίρνει μεταβλητές Boolean — trues και falses, 1s και 0s — και βγάζει είτε true είτε false, 1 ή 0. Και όπως ένας αλγόριθμος, ένα κύκλωμα περιγράφει μια διαδικασία για την παραγωγή μιας εξόδου με οποιαδήποτε είσοδο.

«Καταλαβαίνω ότι οι άνθρωποι άρχισαν να εργάζονται για την πολυπλοκότητα του κυκλώματος επειδή αποφάσισαν ότι οι μηχανές Turing ήταν πολύ περίπλοκες», είπε. Ράιαν Ουίλιαμς, θεωρητικός της πολυπλοκότητας στο MIT. «Μπορούμε να μελετήσουμε κυκλώματα πύλη προς πύλη».

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

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

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

Αυτή ήταν η στρατηγική που ακολούθησαν οι περισσότεροι θεωρητικοί της πολυπλοκότητας τη δεκαετία του 1980. Και οι πιθανότητες ήταν με το μέρος τους. Η Σάνον είχε αποδείχθηκε το 1949 ότι σχεδόν κάθε πίνακας αληθείας Boole (ο οποίος είναι απλώς ένας μακρύς κατάλογος όλων των πιθανών εισόδων και εξόδων μιας Boolean συνάρτησης σταθερού μεγέθους) έχει πολυπλοκότητα κυκλώματος που είναι πρακτικά όσο το δυνατόν υψηλότερη. Χρησιμοποίησε ένα εκπληκτικά απλό επιχείρημα: Υπάρχουν πολύ λιγότεροι τρόποι να συνδυάσετε έναν μικρό αριθμό πυλών από ό,τι υπάρχουν τρόποι να συνδυάσετε πολλές πύλες.

«Απλώς δεν υπάρχουν αρκετά μικρά σιρκουί για να κυκλοφορήσουν», είπε ο Aaronson.

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

Crypto Bros

Στην αρχή, η πρόοδος ήταν ραγδαία. Το 1981 ο Sipser και δύο συνεργάτες του αποδείχθηκε ότι μια συγκεκριμένη Boolean συνάρτηση ήταν σίγουρα δύσκολο να υπολογιστεί εάν χρησιμοποιούσαν κυκλώματα με ορισμένους περιορισμούς σχετικά με τον τρόπο διάταξης των πυλών.

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

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

«Ήμουν απλώς τυχερός που δεν ήξερα πόσο δύσκολο ήταν αυτό το πρόβλημα», είπε ο Razborov. «Διαφορετικά ίσως δεν θα είχα καν ξεκινήσει».

Ο Razborov ανέλυσε κυκλώματα που περιείχαν μόνο πύλες AND και OR, και αποδείχθηκε ότι μια συγκεκριμένη συνάρτηση ήταν δύσκολο να υπολογιστεί χρησιμοποιώντας τέτοια κυκλώματα, ανεξάρτητα από το πώς ήταν διατεταγμένες οι πύλες - επιπλέον, αυτή η συνάρτηση ήταν γνωστό ότι ήταν NP-πλήρη. Το μόνο που έπρεπε να κάνουν οι ερευνητές για να επιλύσουν το P έναντι του NP ήταν να επεκτείνουν τις τεχνικές του Razborov σε κυκλώματα με πύλες ΟΧΙ.

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

Στις Ηνωμένες Πολιτείες, ο Rudich συλλογιζόταν την ίδια ερώτηση. Αυτός και ο Impagliazzo ήταν συμμαθητές στο κολέγιο που είχαν πάει μαζί στο μεταπτυχιακό. Η φιλία τους είχε πυροδοτηθεί από μια κοινή γοητεία με τις αυτοαναφορικές αποδείξεις των Gödel και Turing και τις επιπτώσεις τους στα θεμέλια των μαθηματικών και της επιστήμης των υπολογιστών.

«Το αστείο μας ήταν ότι επρόκειτο να πάρουμε ένα κουμπί που έγραφε «αυτοαναφορά»», είπε ο Impagliazzo.

Ως μεταπτυχιακοί φοιτητές, τόσο ο Rudich όσο και ο Impagliazzo εργάστηκαν στα θεμέλια της θεωρητικής πολυπλοκότητας της κρυπτογραφίας, ένα θέμα που προσφέρει ίσως το καλύτερο πρακτικό κίνητρο για την απόπειρα απόδειξης P ≠ NP. Οι κρυπτογράφοι αποκρύπτουν μυστικά μηνύματα κρύβοντάς τα σε «ψευδοτυχαία» — ένα μήνυμα κρυπτογραφημένο με αυτόν τον τρόπο θα μοιάζει με ένα τυχαίο συνονθύλευμα αριθμών σε οποιονδήποτε κρυφακούει, αλλά εξακολουθεί να μπορεί να αποκωδικοποιηθεί από τον επιδιωκόμενο παραλήπτη. Αλλά πώς μπορείτε να είστε βέβαιοι ότι ένας επίδοξος υποκλοπής θα δυσκολευτεί πολύ να παραβιάσει τον κώδικα;

Εκεί μπαίνει η θεωρία της πολυπλοκότητας. Οι μέθοδοι κρυπτογράφησης που χρησιμοποιούνται ευρέως σήμερα βασίζονται όλες σε φαινομενικά δύσκολα προβλήματα NP — για να αποκρυπτογραφήσει το μήνυμα, ένας εισβολέας θα χρειαζόταν έναν γρήγορο αλγόριθμο που δεν έχει ανακαλυφθεί ακόμη για την επίλυση του προβλήματος. Για να αποδείξετε ότι αυτές οι μέθοδοι είναι πραγματικά ασφαλείς, ένα πράγμα που πρέπει να κάνετε είναι να αποδείξετε ότι P ≠ NP. Χωρίς απόδειξη, είπε ο Sipser, το μόνο που μπορείτε να κάνετε είναι «να ελπίζετε ότι όποιος και αν προσπαθείτε να κρατήσετε το μυστικό δεν είναι καλύτερος μαθηματικός από εσάς».

Μολονότι συναρπαστική από μόνη της, η κρυπτογραφία φαινόταν πολύ μακριά από τα αυτοαναφορικά επιχειρήματα που είχαν αρχικά προσελκύσει τους Rudich και Impagliazzo στο πεδίο. Αλλά καθώς ο Ρούντιτς προσπαθούσε να καταλάβει γιατί η προσέγγιση της πολυπλοκότητας του κυκλώματος είχε σταματήσει, άρχισε να συνειδητοποιεί ότι τελικά τα δύο θέματα δεν ήταν τόσο μακριά. Η στρατηγική που είχαν υιοθετήσει οι ερευνητές στις προσπάθειές τους να αποδείξουν ότι το P ≠ NP είχε έναν αυτοκαταστροφικό χαρακτήρα που θύμιζε τη διάσημη πρόταση του Gödel «αυτή η δήλωση είναι αναπόδεικτη» — και η κρυπτογραφία θα μπορούσε να βοηθήσει να εξηγηθεί γιατί. Στη Ρωσία, ο Razborov ανακάλυψε μια παρόμοια σύνδεση περίπου την ίδια εποχή. Αυτοί ήταν οι σπόροι του φραγμού των φυσικών αποδείξεων.

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

Ένα σκληρό αστείο

Το 1994, ο Razborov και ο Rudich συνειδητοποίησαν ότι είχαν βρει παρόμοιες ιδέες και άρχισαν να συνεργάζονται για να συνδυάσουν τα αποτελέσματά τους. Πρώτα παρατήρησαν ότι όλες οι προηγούμενες προσπάθειες για να αποδείξουν το P ≠ NP χρησιμοποιώντας την πολυπλοκότητα του κυκλώματος είχαν υιοθετήσει την ίδια γενική στρατηγική: Προσδιορίστε μια ειδική ιδιότητα μιας NP-πλήρης συνάρτησης Boole, και στη συνέχεια αποδείξτε ότι καμία εύκολη στον υπολογισμό συνάρτηση δεν θα μπορούσε να μοιραστεί αυτήν την ιδιότητα. Αυτό θα έδειχνε ότι η επιλεγμένη NP-complete συνάρτηση ήταν πραγματικά δύσκολο να υπολογιστεί, αποδεικνύοντας P ≠ NP.

Ο Sipser, ο Razborov και άλλοι είχαν χρησιμοποιήσει την ίδια στρατηγική με επιτυχία για να αποδείξουν τα πιο περιορισμένα αποτελέσματά τους, και σε κάθε περίπτωση, η ειδική ιδιότητα που εντόπισαν οι ερευνητές ήταν κοινή από τις περισσότερες συναρτήσεις Boole. Οι Razborov και Rudich επινόησαν τον όρο «φυσική απόδειξη» για να αναφερθούν σε αυτήν την περίπτωση όπου το ακίνητο ήταν ευρέως κοινό, απλώς και μόνο επειδή δεν υπήρχε γνωστή εναλλακτική. Εάν ήταν δυνατές οι «αφύσικες» αποδείξεις, θα έπρεπε να είναι πολύ αντιφατικές και να αξίζουν το όνομα.

Οι Razborov και Rudich απέδειξαν τότε το κύριο αποτέλεσμά τους: Μια φυσική απόδειξη του P ≠ NP θα απαιτούσε μια πολύ ολοκληρωμένη κατανόηση του τρόπου με τον οποίο διαφέρουν οι εύκολες και δύσκολες συναρτήσεις, και αυτή η γνώση θα μπορούσε επίσης να τροφοδοτήσει έναν γρήγορο αλγόριθμο για εύκολο εντοπισμό -υπολογισμός συναρτήσεων ακόμα κι αν είναι επιφανειακά περίπλοκες. Εάν οι θεωρητικοί της πολυπλοκότητας είχαν πετύχει μια φυσική απόδειξη του P ≠ NP, θα είχαν ανακαλύψει έναν σχεδόν αλάνθαστο τρόπο για να ρίξουν μια ματιά σε έναν αυθαίρετο πίνακα αλήθειας και να καθορίσουν εάν η αντίστοιχη συνάρτηση είχε υψηλή ή χαμηλή πολυπλοκότητα κυκλώματος - ένα πολύ ισχυρότερο και πιο γενικό αποτέλεσμα από είχαν βαλθεί να αποδείξουν.

«Σχεδόν δεν μπορείτε παρά να πάρετε περισσότερα από όσα είχατε παζαρέψει», είπε ο Carmosino.

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

Για να κατανοήσετε αυτή τη σύνδεση, φανταστείτε να κοιτάζετε τη στήλη εξόδου στον πίνακα αλήθειας μιας συνάρτησης Boole με πολλές μεταβλητές εισόδου και να αντικαθιστάτε κάθε "true" με 1 και κάθε "false" με 0:

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

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

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

«Αν πιστεύεις στη σκληρότητα, τότε θα πρέπει να πιστεύεις ότι είναι δύσκολο να αποδείξεις τη σκληρότητα», είπε ο Kabanets.

Μέσα στο Metaverse

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

«Υπάρχει αυτή η διαίσθηση ότι «ω, επειδή P ≠ NP, είναι δύσκολο να αποδειχθεί ότι P ≠ NP», είπε ο Williams. «Αλλά για να καταλάβετε ακόμη και αυτή τη διαίσθηση, πρέπει να αρχίσετε να σκέφτεστε το καθήκον να αποδείξετε κάτι σαν το P ≠ NP ως υπολογιστικό πρόβλημα».

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

«Ήθελα να κάνω κάτι πιο ακαδημαϊκό», θυμάται ο Kabanets. «Και ήμουν επίσης περίεργος να δω τον κόσμο». Μετακόμισε στον Καναδά για μεταπτυχιακό και εκεί έμαθε για το φράγμα των φυσικών αποδείξεων. Όπως και ο Carmosino, έτσι και ο Kabanets ήταν συγκλονισμένος με το αποτέλεσμα. «Φαινόταν πολύ βαθύ ότι έχετε αυτή τη σύνδεση», είπε.

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

Η εργασία των Kabanets και Cai τόνισε ένα υπολογιστικό πρόβλημα που υπονοείται στη διατύπωση του φραγμού των φυσικών αποδείξεων από τους Razborov και Rudich: Δεδομένου του πίνακα αλήθειας μιας Boolean συνάρτησης, καθορίστε εάν έχει υψηλή ή χαμηλή πολυπλοκότητα κυκλώματος. Το ονόμασαν αυτό το πρόβλημα ελάχιστου μεγέθους κυκλώματος ή MCSP.

Το MCSP είναι ένα ουσιαστικό πρόβλημα μετα-πολυπλοκότητας: ένα υπολογιστικό πρόβλημα του οποίου το θέμα δεν είναι η θεωρία γραφημάτων ή άλλο εξωτερικό θέμα, αλλά η ίδια η θεωρία πολυπλοκότητας. Πράγματι, είναι σαν μια ποσοτική εκδοχή του ερωτήματος που ώθησε τους θεωρητικούς της πολυπλοκότητας να αντιμετωπίσουν το P έναντι του NP χρησιμοποιώντας την προσέγγιση πολυπλοκότητας κυκλώματος στη δεκαετία του 1980: Ποιες συναρτήσεις Boolean είναι δύσκολο να υπολογιστούν και ποιες είναι εύκολες;

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

Οι θεωρητικοί της πολυπλοκότητας δεν ανησυχούν για αυτόν τον μαγικό αλγόριθμο που τους βάζει εκτός δουλειάς - δεν πιστεύουν ότι υπάρχει καθόλου, επειδή οι Razborov και Rudich έδειξαν ότι οποιοσδήποτε τέτοιος αλγόριθμος για τη διάκριση πινάκων αλήθειας υψηλής πολυπλοκότητας από αυτούς χαμηλής πολυπλοκότητας θα έκανε κρυπτογραφία αδύνατο. Αυτό σημαίνει ότι το MCSP είναι πιθανότατα ένα δύσκολο υπολογιστικό πρόβλημα. Αλλά πόσο δύσκολο είναι; Είναι NP-complete, όπως το πρόβλημα του μονοπατιού Hamilton και σχεδόν κάθε άλλο πρόβλημα με το οποίο αντιμετώπισαν οι ερευνητές τη δεκαετία του 1960;

Για προβλήματα στο NP, "πόσο δύσκολο είναι;" είναι συνήθως αρκετά εύκολο να απαντηθεί, αλλά το MCSP φαινόταν να είναι ένα περίεργο ακραίο στοιχείο. «Έχουμε πολύ λίγα προβλήματα που δεν έχουν συνδεθεί με αυτό το νησί με πλήρη προβλήματα NP, παρόλο που φαίνονται δύσκολα», είπε ο Kabanets.

Ο Kabanets γνώριζε ότι αυτός και ο Cai δεν ήταν οι πρώτοι που σκέφτηκαν το πρόβλημα που είχαν ονομάσει MCSP. Σοβιετικοί μαθηματικοί είχαν μελετήσει ένα πολύ παρόμοιο πρόβλημα ξεκινώντας από τη δεκαετία του 1950, σε μια πρώιμη προσπάθεια να κατανοήσουν την εγγενή δυσκολία διαφορετικών υπολογιστικών προβλημάτων. Ο Leonid Levin είχε παλέψει μαζί του ενώ ανέπτυξε αυτό που θα γινόταν η θεωρία της NP-πληρότητας στα τέλη της δεκαετίας του 1960, αλλά δεν μπορούσε να αποδείξει ότι ήταν NP-complete και δημοσίευσε τη θεμελιώδη εργασία του χωρίς αυτήν.

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

«Είναι, κατά μία έννοια, μετα-μετα-πολυπλοκότητα», είπε Ραχούλ Σαντάναμ, θεωρητικός της πολυπλοκότητας στο Πανεπιστήμιο της Οξφόρδης.

Ήταν όμως μέχρι κάτω η σκληρότητα ή υπήρχε τουλάχιστον κάποιος τρόπος να καταλάβουμε γιατί οι ερευνητές δεν είχαν καταφέρει να αποδείξουν ότι το MCSP ήταν NP-complete; Ο Kabanets ανακάλυψε ότι, ναι, υπήρχε λόγος: Η δυσκολία κατανόησης της πολυπλοκότητας του κυκλώματος λειτουργεί σαν εμπόδιο σε οποιαδήποτε γνωστή στρατηγική για την απόδειξη της NP-πληρότητας του MCSP — ένα πρόβλημα που αφορά τη δυσκολία κατανόησης της πολυπλοκότητας του κυκλώματος. Η στριμμένη, αυτοκαταστροφική λογική του φραγμού των φυσικών αποδείξεων φαινόταν αναπόφευκτη.

Είναι επίσης πιθανό το MCSP να μην είναι NP-complete, αλλά και αυτό φαίνεται απίθανο — ορισμένες απλούστερες παραλλαγές του προβλήματος είναι ήδη γνωστό ότι είναι NP-complete.

«Απλώς δεν έχουμε ένα ωραίο μέρος για να το τοποθετήσουμε που να το συσχετίζει άμεσα με όλα τα άλλα προβλήματα που μελετάμε», είπε ο Impagliazzo.

Ο Kabanets είχε φωτίσει την περίεργη συμπεριφορά του MCSP, αλλά δεν ήξερε πώς να κάνει περαιτέρω πρόοδο. Η έρευνα μετα-πολυπλοκότητας επιβραδύνθηκε σταδιακά. Θα άνθιζε ξανά 16 χρόνια αργότερα, όταν οι ερευνητές ανακάλυψαν μια εκπληκτική σύνδεση με ένα άλλο θεμελιώδες ερώτημα: Πόσο δύσκολο είναι να λύσετε προβλήματα εάν ενδιαφέρεστε μόνο για τη λήψη της σωστής απάντησης τις περισσότερες φορές;

Ο Πόλεμος των Κόσμων

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

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

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

Ήταν στην πραγματικότητα ο Levin που ξεκίνησε την αυστηρή μελέτη της πολυπλοκότητας της μέσης περίπτωσης, μια δεκαετία μετά την πρωτοποριακή εργασία του για την πληρότητα των NP. Στα χρόνια που μεσολάβησαν, είχε έρθει σε σύγκρουση με τις σοβιετικές αρχές - ήταν ένας ασεβής ταραχοποιός που υπονόμευε περιστασιακά τις πατριωτικές δραστηριότητες στη νεολαία του Κομμουνιστικού Κόμματος. Το 1972, του αρνήθηκαν το διδακτορικό του για ρητά πολιτικούς λόγους.

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

Ο Levin μετανάστευσε στις Ηνωμένες Πολιτείες το 1978 και στα μέσα της δεκαετίας του 1980 έστρεψε την προσοχή του στην πολυπλοκότητα της μέσης υπόθεσης. Άρχισε να συνεργάζεται με άλλους για να αναπτύξει περαιτέρω τη θεωρία, συμπεριλαμβανομένου του Impagliazzo, ενός μεταπτυχιακού φοιτητή εκείνη την εποχή. Όμως, ακόμη και καθώς έκαναν πρόοδο, ο Impagliazzo διαπίστωσε ότι οι ερευνητές συχνά μιλούσαν ο ένας δίπλα στον άλλο. Ήθελε να φέρει τους πάντες στην ίδια σελίδα, και δεν βοήθησε το γεγονός ότι τα χαρτιά του Levin ήταν περίφημα συνοπτικά — αυτό που ξεκίνησε το πεδίο μέσης πολυπλοκότητας υπόθεσης ήταν λιγότερο από δύο σελίδες.

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

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

Από τότε που εμφανίστηκε η εργασία του Impagliazzo, οι ερευνητές ονειρεύτηκαν να εξαλείψουν μέρη του μικροσκοπικού πολυσύμπαντος του - περιορίζοντας το χώρο των δυνατοτήτων αποδεικνύοντας ότι ορισμένοι από τους κόσμους τελικά δεν είναι δυνατοί. Δύο κόσμοι είναι ιδιαίτερα δελεαστικοί στόχοι: εκείνοι όπου η κρυπτογράφηση είναι αδύνατη παρόλο που P ≠ NP.

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

Αυτοί οι δύο κόσμοι αποδεικνύεται ότι είναι στενά συνδεδεμένοι με προβλήματα μετα-πολυπλοκότητας — ειδικότερα, η μοίρα του Heuristica συνδέεται με το μακροχρόνιο ερώτημα εάν το MCSP είναι NP-πλήρες. Η ερώτηση που γοήτευσε τον Καμπάνετς και παραπλανούσε τον Λέβιν τόσο καιρό πριν δεν είναι απλή περιέργεια: Διακυβεύεται ένας ολόκληρος κόσμος.

Για να αποκλειστεί το Heuristica, οι ερευνητές θα έπρεπε να καταρρίψουν τη διάκριση μεταξύ της πολυπλοκότητας της χειρότερης περίπτωσης και της μέσης περίπτωσης — δηλαδή, θα έπρεπε να αποδείξουν ότι οποιοσδήποτε υποθετικός αλγόριθμος που λύνει σωστά ένα πρόβλημα NP-complete στις περισσότερες εισόδους μπορεί πραγματικά να το λύσει. σε κάθε περίπτωση. Αυτό το είδος σύνδεσης, που ονομάζεται μείωση από τη χειρότερη περίπτωση έως τη μέση περίπτωση, είναι γνωστό ότι υπάρχει για ορισμένα προβλήματα, αλλά κανένα από αυτά δεν είναι πλήρες, επομένως αυτά τα αποτελέσματα δεν υπονοούν κάτι πιο γενικό. Η εξάλειψη της Heuristica θα οδηγούσε τους κρυπτογράφους στα μισά του δρόμου για να πραγματοποιήσουν το όνειρο της ασφαλούς κρυπτογράφησης με βάση τη μοναδική υπόθεση ότι P ≠ NP.

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

Οι ερευνητές θα έπρεπε να βρουν μια άλλη προσέγγιση και τώρα πιστεύουν ότι το MCSP μπορεί να είναι απλώς το πρόβλημα που χρειάζονται. Αλλά αυτό δεν θα γινόταν ξεκάθαρο για πάνω από μια δεκαετία. Η πρώτη ματιά της σύνδεσης προέκυψε από την επίμονη γοητεία του Marco Carmosino με το φράγμα των φυσικών αποδείξεων.

Ο Carmosino συνάντησε για πρώτη φορά την έρευνα μετα-πολυπλοκότητας ως μεταπτυχιακός φοιτητής μέσω του α χαρτί 2013 από τον Kabanets και τέσσερις άλλους ερευνητές, οι οποίοι ανέπτυξαν περαιτέρω την προσέγγιση του φραγμού των φυσικών αποδείξεων που ο Kabanets είχε πρωτοπορήσει περισσότερο από μια δεκαετία νωρίτερα. Απλώς ενίσχυσε την πεποίθησή του ότι υπήρχαν ακόμη περισσότερα να μάθει από την κλασική εργασία του Razborov και του Rudich.

«Είχα εμμονή με αυτό το χαρτί εκείνη την εποχή», είπε ο Carmosino. "Τίποτα δεν άλλαξε."

Η εμμονή τελικά απέδωσε καρπούς κατά τη διάρκεια μιας επίσκεψης σε ένα εξάμηνο εργαστήριο στο Πανεπιστήμιο της Καλιφόρνια στο Μπέρκλεϋ, όπου περνούσε τον περισσότερο χρόνο του μιλώντας με τους Impagliazzo, Kabanets και Antonina Kolokolova, θεωρητικός της πολυπλοκότητας στο Memorial University of Newfoundland που είχε συνεργαστεί με τον Kabanets στην εργασία του 2013. Ο Carmosino είχε δουλέψει με τους τρεις τους μια φορά στο παρελθόν, και αυτή η επιτυχημένη συνεργασία του έδωσε την αυτοπεποίθηση να τους γεμίσει με ερωτήσεις σχετικά με το θέμα που τον γοήτευε περισσότερο.

«Καλούσε τους ανθρώπους με καλό τρόπο», θυμάται ο Kabanets.

Αρχικά, ο Carmosino είχε νέες ιδέες για την απόδειξη της πληρότητας NP για την έκδοση του MCSP που είχε εμφανιστεί στο άρθρο του Razborov και του Rudich σχετικά με το φράγμα των φυσικών αποδείξεων. Αλλά αυτές οι ιδέες δεν βγήκαν έξω. Αντίθετα, μια παρατήρηση του Impagliazzo έκανε τους τέσσερις ερευνητές να συνειδητοποιήσουν ότι το φράγμα των φυσικών αποδείξεων θα μπορούσε να αποφέρει ισχυρότερους αλγόριθμους από ό,τι είχε καταλάβει κανείς - υπήρχε ένας μυστικός χάρτης χαραγμένος στο οδόφραγμα.

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

«Δεν ήταν προφανές ότι μια τέτοια σύνδεση θα υπήρχε καθόλου», είπε ο Impagliazzo.

Ένας γρήγορος αλγόριθμος για το MCSP είναι καθαρά υποθετικός για γενικά κυκλώματα Boolean: Δεν μπορεί να υπάρξει εκτός εάν αποδειχθεί ότι το MCSP είναι ένα εύκολο υπολογιστικό πρόβλημα, παρά όλα τα στοιχεία για το αντίθετο, και αυτό σημαίνει ότι ο αλγόριθμος μάθησης που υπονοείται από την εργασία των τεσσάρων ερευνητών είναι εξίσου υποθετικό.

Αλλά για μερικές απλούστερες εκδόσεις του MCSP — διάκριση πινάκων αλήθειας υψηλής πολυπλοκότητας από πίνακες χαμηλής πολυπλοκότητας όταν υπάρχουν συγκεκριμένοι περιορισμοί στα κυκλώματα — οι γρήγοροι αλγόριθμοι είναι γνωστοί εδώ και πολλά χρόνια. Η εργασία των Carmosino, Impagliazzo, Kabanets και Kolokolova έδειξε ότι αυτοί οι αλγόριθμοι θα μπορούσαν να μετατραπούν σε αλγόριθμους μάθησης που ήταν επίσης περιορισμένοι αλλά ακόμα πιο ισχυροί από οποιονδήποτε άλλον που οι ερευνητές είχαν κατανοήσει προηγουμένως σε ένα τόσο αυστηρό θεωρητικό επίπεδο.

«Κάπως η αυτοαναφορική τους γεύση σάς δίνει τη δυνατότητα να κάνετε πράγματα που φαινομενικά δεν μπορείτε να κάνετε με πιο τυπικά προβλήματα», είπε ο Ilango.

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

Πάνω απ 'όλα, ήταν μια απόδειξη του πόσο μακριά μπορούν να φτάσουν οι ερευνητές κάνοντας απλές ερωτήσεις σχετικά με εμπόδια που στην αρχή φαίνεται απλώς να εμποδίζουν την πρόοδό τους.

«Αυτό το είδος δυαδικότητας είναι ένα θέμα για τα τελευταία τουλάχιστον 30 ή 40 χρόνια πολυπλοκότητας», είπε ο Impagliazzo. «Τα εμπόδια είναι συχνά οι ευκαιρίες».

Μερική πίστωση

Η πρόοδος έχει επιταχυνθεί μόνο τα χρόνια από τότε που ο Carmosino και οι συνεργάτες του δημοσίευσαν την εργασία τους.

«Συμβαίνουν νέα πράγματα», είπε η Kolokolova. «Υπάρχουν πολλοί πραγματικά, πολύ ευφυείς μικροί ερευνητές».

Ο Ilango είναι ένας από αυτούς τους νέους ερευνητές — στα πρώτα τρία χρόνια του μεταπτυχιακού, αντιμετώπισε το τρομακτικό ανοιχτό πρόβλημα της απόδειξης του MCSP NP-complete χρησιμοποιώντας μια στρατηγική δύο όψεων: απόδειξη της πληρότητας NP για απλούστερη εκδόσεις του MCSP, όπως έκαναν οι ερευνητές πολυπλοκότητας κυκλώματος όταν επιτέθηκαν στο P έναντι του NP στη δεκαετία του 1980, ενώ απέδειξαν επίσης την πληρότητα NP για πιο περίπλοκες εκδόσεις, που διαισθητικά φαίνονται πιο δύσκολα και επομένως είναι ίσως πιο εύκολο να αποδειχθούν δύσκολα.

Ο Ilango πιστώνει το ενδιαφέρον του για τη μετα-πολυπλοκότητα Έρικ Άλεντερ, θεωρητικός της πολυπλοκότητας στο Πανεπιστήμιο Rutgers και ένας από τους λίγους ερευνητές που συνέχισαν να εργάζονται για τη μετα-πολυπλοκότητα στη δεκαετία του 2000 και στις αρχές της δεκαετίας του 2010. «Ο ενθουσιασμός του ήταν μεταδοτικός», είπε ο Ιλάνγκο.

Ένας άλλος νεαρός ερευνητής εμπνευσμένος από τον Allender είναι Shuichi Hirahara, τώρα καθηγητής στο Εθνικό Ινστιτούτο Πληροφορικής στο Τόκιο. Ενώ ήταν ακόμη μεταπτυχιακός φοιτητής το 2018, ο Hirahara αποκάλυψε την πραγματική έκταση της σχέσης μεταξύ μετα-πολυπλοκότητας και πολυπλοκότητας μέσης υπόθεσης που είχαν ανακαλύψει ο Carmosino και οι συν-συγγραφείς του. Αυτοί οι τέσσερις ερευνητές είχαν βρει μια σύνδεση μεταξύ της πολυπλοκότητας της μέσης περίπτωσης ενός προβλήματος - MCSP - και της πολυπλοκότητας στη χειρότερη περίπτωση ενός άλλου - της μάθησης Boole. Η Hirahara ανέπτυξε τις τεχνικές της περαιτέρω σε τάση μείωση της χειρότερης προς τη μέση περίπτωση για το MCSP. Το αποτέλεσμά του υποδηλώνει ότι ένας υποθετικός αλγόριθμος MCSP μέσης περίπτωσης, όπως αυτός που είχαν εξετάσει ο Carmosino και οι συνάδελφοί του, θα ήταν στην πραγματικότητα αρκετά ισχυρός για να λύσει μια ελαφρώς διαφορετική έκδοση του MCSP χωρίς να κάνει λάθη.

Το αποτέλεσμα της Hirahara είναι συναρπαστικό επειδή πολλοί ερευνητές υποπτεύονται ότι το MCSP είναι NP-complete, σε αντίθεση με όλα τα άλλα προβλήματα για τα οποία είναι γνωστές οι μειώσεις από τη χειρότερη έως τη μέση περίπτωση. Εάν μπορούν να επεκτείνουν τα αποτελέσματα της Hirahara για να καλύψουν όλους τους αλγόριθμους μέσης περίπτωσης και στη συνέχεια να αποδείξουν ότι το MCSP είναι NP-complete, αυτό θα αποδείξει ότι δεν ζούμε στην Heuristica.

«Αυτό θα ήταν πραγματικά ένα καταστροφικό αποτέλεσμα», είπε ο Santhanam.

Το να αποδείξουμε ότι το MCSP είναι NP-complete μπορεί να φαίνεται σαν μια μεγάλη παραγγελία — σε τελική ανάλυση, το ερώτημα είναι ανοιχτό για περισσότερα από 50 χρόνια. Αλλά μετά από ένα επανάσταση πέρυσι από τη Hirahara, οι ερευνητές είναι τώρα πολύ πιο κοντά από ό,τι θα περίμενε κανείς πριν από μερικά χρόνια.

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

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

Αυτό το αποτέλεσμα ενθάρρυνε τους ερευνητές στη μετα-πολυπλοκότητα ακόμη περισσότερο από την προηγούμενη εργασία της Hirahara, και άλλοι ερευνητές το πρόσεξαν επίσης — ο θεωρητικός της πολυπλοκότητας και blogger Lance Fortnow το ονόμασε ως αποτέλεσμα της χρονιάς. Αυτό συμβαίνει επειδή η αντιμετώπιση τέτοιων εκδόσεων «μερικής λειτουργίας» υπολογιστικών προβλημάτων ήταν ένα βασικό ενδιάμεσο βήμα σε άλλες αποδείξεις πληρότητας NP.

«Είναι καταπληκτική δουλειά», είπε ο Williams. «Όλοι πίστευαν ότι αυτά τα μερικά προβλήματα ήταν περίπου η ίδια δυσκολία με το πλήρες πρόβλημα».

Εξακολουθούν να υπάρχουν εμπόδια στην απόδειξη της πληρότητας NP για την πλήρη έκδοση του MCSP. Αλλά κανένα δεν είναι το είδος των φραγμών που υποδηλώνουν ότι χρειάζεται μια εντελώς νέα εργαλειοθήκη — μπορεί απλώς να είναι θέμα εύρεσης του σωστού τρόπου συνδυασμού γνωστών τεχνικών. Μια απόδειξη θα διευκόλυνε τελικά το καθεστώς ενός από τα λίγα προβλήματα που αντιστέκονταν στην ταξινόμηση για όσο διάστημα υπήρχε η θεωρία πολυπλοκότητας. Μέσω email, ο Levin έγραψε: «Θα με ταπεινώσει να δείξω ότι ήμουν ηλίθιος που δεν μπόρεσα να το δω :-).»

Τα κομμάτια που λείπουν

Το MCSP δεν είναι καν το μόνο πρόβλημα μετα-πολυπλοκότητας που οδήγησε σε μια σημαντική ανακάλυψη. Το 2020, ο κρυπτογράφος Cornell Tech Πέρασμα Ραφαέλ και ο μεταπτυχιακός φοιτητής του Yanyi Liu ανακάλυψε μια σύνδεση μεταξύ ενός διαφορετικού προβλήματος μετα-πολυπλοκότητας και ενός θεμελιώδους κρυπτογραφικού πρωτοκόλλου που ορίζει τα όρια μεταξύ Heuristica και Pessiland, του χειρότερου κόσμου του Impagliazzo (όπου τα προβλήματα NP-πλήρης είναι δύσκολα στη μέση περίπτωση, αλλά η κρυπτογράφηση είναι ακόμα αδύνατη). Αυτό καθιστά το πρόβλημα που μελέτησαν έναν κύριο υποψήφιο για μια επίθεση στο Pessiland και τους πιο πρόσφατη δουλειά δείχνει ότι θα μπορούσε να λειτουργήσει και ενάντια στην Heuristica.

«Λείπουν διάφορα κομμάτια του παζλ», είπε ο Πας. «Για μένα είναι απλά μαγικό που αυτά τα πεδία συνδέονται τόσο στενά».

Η Hirahara προειδοποιεί ότι οι προκλήσεις εξακολουθούν να περιμένουν τους ερευνητές που σκοπεύουν να εξοντώσουν τους κόσμους που δημιούργησε ο Impagliazzo πριν από 30 χρόνια. «Θα ήθελα να πω ότι κάποια στιγμή οι Heuristica και Pessiland θα αποκλειστούν, αλλά δεν είμαι σίγουρος πόσο κοντά είμαστε», είπε.

Πολλοί ερευνητές αναμένουν ότι η μεγαλύτερη δυσκολία θα είναι να γεφυρωθεί ένα φαινομενικά αβλαβές χάσμα μεταξύ δύο διαφορετικών μοντέλων μέσης πολυπλοκότητας υπόθεσης. Οι κρυπτογράφοι συνήθως μελετούν αλγόριθμους μέσης περίπτωσης που κάνουν λάθη και προς τις δύο κατευθύνσεις, περιστασιακά χαρακτηρίζοντας λανθασμένα τις τυχαίες συμβολοσειρές ως ψευδοτυχαίες και το αντίστροφο. Εν τω μεταξύ, οι μειώσεις από τη χειρότερη έως τη μέση περίπτωση της Hirahara λειτουργούν για αλγόριθμους μέσης περίπτωσης που κάνουν μόνο τον πρώτο τύπο λάθους. Λεπτές διακρίσεις όπως αυτή μπορούν να κάνουν μια μεγάλη διαφορά στη θεωρία πολυπλοκότητας. Όμως, παρά αυτό το εμπόδιο και πολλά άλλα, ο Allender δεν μπορεί παρά να ακούσει μια νότα φυλαγμένης αισιοδοξίας.

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

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

«Είναι πραγματικά υπέροχο που είναι τόσο δύσκολο», είπε ο Carmosino. «Δεν πρόκειται να βαρεθώ ποτέ».

Σημείωση του συντάκτη: Ο Scott Aaronson είναι μέλος του Quanta Magazine'S συμβουλευτική Επιτροπή.