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

Ο David Gamarnik, καθηγητής επιχειρησιακής έρευνας στο MIT Sloan School of Management και στο Ινστιτούτο Δεδομένων, Συστημάτων και Κοινωνίας, εστιάζει την προσοχή του στην τελευταία, λιγότερο μελετημένη κατηγορία προβλημάτων, τα οποία σχετίζονται περισσότερο με τον καθημερινό κόσμο, επειδή εμπλέκω τυχαιότητα— αναπόσπαστο χαρακτηριστικό των φυσικών συστημάτων. Αυτός και οι συνάδελφοί του έχουν αναπτύξει ένα ισχυρό εργαλείο για την ανάλυση αυτών των προβλημάτων που ονομάζεται ιδιότητα επικάλυψης κενού (ή OGP). Ο Gamarnik περιέγραψε τη νέα μεθοδολογία σε ένα πρόσφατο άρθρο στο Πρακτικά της Εθνικής Ακαδημίας Επιστημών.

P NP

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

Η εικασία P ≠ NP δεν έχει ακόμη αποδειχθεί, ωστόσο οι περισσότεροι επιστήμονες υπολογιστών πιστεύουν ότι πολλά γνωστά προβλήματα – συμπεριλαμβανομένου, για παράδειγμα, του προβλήματος του ταξιδιώτη πωλητή – εμπίπτουν σε αυτήν την απίστευτα δύσκολη κατηγορία. Η πρόκληση στο παράδειγμα του πωλητή είναι να βρείτε τη συντομότερη διαδρομή, από άποψη απόστασης ή χρόνου, μέσω Ν διαφορετικών πόλεων. Η διαχείριση της εργασίας γίνεται εύκολα όταν N=4, επειδή υπάρχουν μόνο έξι πιθανές διαδρομές που πρέπει να ληφθούν υπόψη. Αλλά για 30 πόλεις, υπάρχουν περισσότερες από 10³⁰ πιθανές διαδρομές και οι αριθμοί αυξάνονται δραματικά από εκεί. Η μεγαλύτερη δυσκολία έρχεται στο σχεδιασμό ενός αλγόριθμος που λύνει γρήγορα το πρόβλημα σε όλες τις περιπτώσεις, για όλες τις ακέραιες τιμές του N. Οι επιστήμονες υπολογιστών είναι βέβαιοι, με βάση την αλγοριθμική θεωρία πολυπλοκότητας, ότι δεν υπάρχει τέτοιος αλγόριθμος, επιβεβαιώνοντας έτσι ότι P ≠ NP.

Υπάρχουν πολλά άλλα παραδείγματα δυσεπίλυτων προβλημάτων όπως αυτό. Ας υποθέσουμε, για παράδειγμα, ότι έχετε έναν τεράστιο πίνακα αριθμών με χιλιάδες σειρές και χιλιάδες στήλες. Μπορείτε να βρείτε, ανάμεσα σε όλους τους πιθανούς συνδυασμούς, την ακριβή διάταξη των 10 σειρών και 10 στηλών έτσι ώστε οι 100 καταχωρήσεις του να έχουν το υψηλότερο δυνατό άθροισμα; «Τις ονομάζουμε εργασίες βελτιστοποίησης», λέει ο Gamarnik, «επειδή προσπαθείτε πάντα να βρείτε τον μεγαλύτερο ή τον καλύτερο—το μεγαλύτερο άθροισμα αριθμών, την καλύτερη διαδρομή μέσω πόλεων και ούτω καθεξής».

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

Κορυφές και κοιλάδες

Για να καταλάβετε τι είναι το OGP, μπορεί πρώτα να είναι διδακτικό να δούμε πώς προέκυψε η ιδέα. Από τη δεκαετία του 1970, οι φυσικοί μελετούν τα περιστρεφόμενα γυαλιά – υλικά με ιδιότητες τόσο υγρών όσο και στερεών που έχουν ασυνήθιστη μαγνητική συμπεριφορά. Η έρευνα στα γυαλιά περιστροφής οδήγησε σε μια γενική θεωρία περίπλοκων συστημάτων που σχετίζεται με προβλήματα στη φυσική, τα μαθηματικά, την επιστήμη των υπολογιστών, την επιστήμη των υλικών και άλλους τομείς. (Αυτό το έργο χάρισε στον Giorgio Parisi το Νόμπελ Φυσικής 2021.)

Ένα ενοχλητικό ζήτημα με το οποίο έχουν παλέψει οι φυσικοί είναι η προσπάθεια πρόβλεψης των ενεργειακών καταστάσεων, και ιδιαίτερα των χαμηλότερων ενεργειακών διαμορφώσεων, διαφορετικών δομών γυαλιού περιστροφής. Η κατάσταση μερικές φορές απεικονίζεται από ένα «τοπίο» από αμέτρητες βουνοκορφές που χωρίζονται από κοιλάδες, όπου ο στόχος είναι να εντοπιστεί η υψηλότερη κορυφή. Σε αυτή την περίπτωση, η υψηλότερη κορυφή αντιπροσωπεύει στην πραγματικότητα τη χαμηλότερη ενεργειακή κατάσταση (αν και θα μπορούσε κανείς να γυρίσει την εικόνα και να αναζητήσει τη βαθύτερη τρύπα). Αυτό αποδεικνύεται ότι είναι ένα πρόβλημα βελτιστοποίησης παρόμοιο σε μορφή με το δίλημμα του περιοδεύοντος πωλητή, εξηγεί ο Gamarnik: “Έχετε αυτή την τεράστια συλλογή από βουνά και ο μόνος τρόπος για να βρείτε το ψηλότερο φαίνεται να είναι ανεβαίνοντας το καθένα”—α Σισύφεια αγγαρεία συγκρίσιμη με το να βρεις βελόνα σε θημωνιά.

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

Σε μια εφημερίδα του 2014, ο Gamarnik και οι συνεργάτες του παρατήρησαν κάτι που προηγουμένως είχε παραβλεφθεί. Σε ορισμένες περιπτώσεις, συνειδητοποίησαν, ότι η διάμετρος κάθε κορυφής θα είναι πολύ μικρότερη από τις αποστάσεις μεταξύ διαφορετικών κορυφών. Κατά συνέπεια, αν κάποιος επρόκειτο να επιλέξει οποιαδήποτε δύο σημεία σε αυτό το εκτεταμένο τοπίο – οποιεσδήποτε δύο πιθανές “λύσεις” – θα ήταν είτε πολύ κοντά (αν προέρχονταν από την ίδια κορυφή) είτε πολύ μακριά (αν αντλούνταν από διαφορετικές κορυφές). Με άλλα λόγια, θα υπήρχε ένα ενδεικτικό «κενό» σε αυτές τις αποστάσεις—είτε μικρό είτε μεγάλο, αλλά τίποτα ενδιάμεσο. Ένα σύστημα σε αυτή την κατάσταση, πρότειναν ο Gamarnik και οι συνεργάτες του, χαρακτηρίζεται από το OGP.

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

Ξεκλειδώνοντας τα μυστικά της αλγοριθμικής πολυπλοκότητας

Η εμφάνιση του OGP μπορεί να βοηθήσει τους ερευνητές να αξιολογήσουν τη δυσκολία δημιουργίας γρήγορων αλγορίθμων για την αντιμετώπιση συγκεκριμένων προβλημάτων. Και τους έχει ήδη δώσει τη δυνατότητα «να μαθηματικά [and] αποκλείει αυστηρά μια μεγάλη κατηγορία αλγορίθμων ως πιθανούς ανταγωνιστές”, λέει ο Gamarnik. “Έχουμε μάθει, συγκεκριμένα, ότι οι σταθεροί αλγόριθμοι—αυτοί των οποίων η έξοδος δεν θα αλλάξει πολύ εάν η είσοδος αλλάξει μόνο λίγο—θα αποτύχουν στην επίλυση αυτού του τύπου του προβλήματος βελτιστοποίησης.” Αυτό το αρνητικό αποτέλεσμα ισχύει όχι μόνο για τους συμβατικούς υπολογιστές, αλλά και για τους κβαντικούς υπολογιστές, και συγκεκριμένα, για τους λεγόμενους “αλγόριθμους βελτιστοποίησης κβαντικής προσέγγισης” (QAOAs), που ορισμένοι ερευνητές ήλπιζαν ότι θα μπορούσαν να λύσουν αυτά τα ίδια προβλήματα βελτιστοποίησης. Τώρα , λόγω των ευρημάτων του Gamarnik και των συν-συγγραφέων του, αυτές οι ελπίδες μετριάστηκαν από την αναγνώριση ότι θα απαιτούνταν πολλά επίπεδα λειτουργιών για να επιτύχουν αλγόριθμοι τύπου QAOA, κάτι που θα μπορούσε να είναι τεχνικά προκλητικό.

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

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

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