Ένα πρόβλημα με εύκολο ήχο αποδίδει αριθμούς πολύ μεγάλους για το σύμπαν μας | Περιοδικό Quanta

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

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

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

Αποδεικνύεται ότι αυτό το παιδικό πρόβλημα είναι παράλογα, σχεδόν γελοιογραφικά περίπλοκο — τόσο περίπλοκο που σχεδόν όλα τα άλλα περίφημα σκληρά υπολογιστικά προβλήματα μοιάζουν με παιδικό παιχνίδι. Προσπαθήστε να ποσοτικοποιήσετε την προσπάθεια που απαιτείται για να λύσετε αυτό το πρόβλημα και σύντομα θα αντιμετωπίσετε αριθμούς τόσο μεγάλους που ακόμη και αν μετρήσετε τα ψηφία τους θα φτάσετε σε αριθμούς που δεν έχετε ακούσει ποτέ. Τέτοιοι αριθμοί συχνά προκαλούν συγκρίσεις με την κλίμακα του σύμπαντος, αλλά ακόμη και αυτές οι αναλογίες υπολείπονται. «Αυτό δεν θα ήταν δίκαιο», είπε Georg Zetzsche, επιστήμονας υπολογιστών στο Ινστιτούτο Max Planck για Συστήματα Λογισμικού στο Kaiserslautern της Γερμανίας. «Το σύμπαν είναι τόσο μικρό».

Εντός πρόσβασης;

Απογυμνωμένο στην ουσία του, το πρόβλημα προσβασιμότητας αφορά μαθηματικά αντικείμενα που ονομάζονται διανύσματα, τα οποία είναι ταξινομημένες λίστες αριθμών. Οι εγγραφές σε αυτές τις λίστες ονομάζονται συνιστώσες και ο αριθμός των συστατικών σε ένα διάνυσμα ονομάζεται διάσταση του. Η απογραφή φρούτων της Αλίκης, για παράδειγμα, μπορεί να περιγραφεί από ένα τετραδιάστατο διάνυσμα (a, b, c, d), τα συστατικά του οποίου αντιπροσωπεύουν πόσα μήλα, μπανάνες, πεπόνια και πορτοκάλια έχει ανά πάσα στιγμή.

Ένα σύστημα προσθήκης διανυσμάτων, ή VAS, είναι μια συλλογή διανυσμάτων που αντιπροσωπεύουν τις πιθανές μεταβάσεις μεταξύ καταστάσεων σε ένα σύστημα. Για την Αλίκη, το διάνυσμα μετάβασης (−1, −1, 1, 0) θα αντιπροσώπευε την ανταλλαγή ενός μήλου και μιας μπανάνας με ένα πεπόνι. Το πρόβλημα προσβασιμότητας VAS ρωτά εάν υπάρχει κάποιος συνδυασμός επιτρεπόμενων μεταβάσεων που μπορεί να σας μεταφέρει από μια συγκεκριμένη αρχική κατάσταση σε μια συγκεκριμένη κατάσταση στόχο — ή, με μαθηματικούς όρους, εάν υπάρχει κάποιο άθροισμα διανυσμάτων μετάβασης που μετατρέπει το αρχικό διάνυσμα στο διάνυσμα στόχο. Υπάρχει μόνο μια σύλληψη: Κανένα στοιχείο του διανύσματος που περιγράφει την κατάσταση του συστήματος δεν μπορεί ποτέ να πέσει κάτω από το μηδέν.

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

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

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

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

The Stuff of Nightmares

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

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

Λίπτον τότε αποδείχθηκε μπορούσε να κατασκευάσει ένα σύστημα μεγέθους n στην οποία η συντομότερη διαδρομή μεταξύ δύο καταστάσεων περιλάμβανε περισσότερες από μεταβάσεις $latex 2^{2^n}$. Αυτό συνεπαγόταν ένα αντίστοιχο διπλό εκθετικό κάτω όριο στην προσπάθεια που απαιτείται για τον προσδιορισμό της προσβασιμότητας στα συστήματά του. Ήταν μια εκπληκτική ανακάλυψη - η διπλή εκθετική ανάπτυξη είναι το υλικό των εφιάλτων των επιστημόνων υπολογιστών. Πράγματι, οι ερευνητές συχνά αμφισβητούν ακόμη και τη συνηθισμένη εκθετική ανάπτυξη, η οποία ωχριά σε σύγκριση: $latex {2^5}= 32$, αλλά $latex 2^{2^5}$ είναι πάνω από 4 δισεκατομμύρια.

Οι περισσότεροι ερευνητές πίστευαν ότι ο Lipton είχε φτιάξει τα πιο περίπλοκα δυνατά συστήματα πρόσθεσης διανυσμάτων, που σημαίνει ότι είχε ανεβάσει το κάτω όριο όσο πιο ψηλά μπορούσε. Το μόνο πράγμα που λείπει, σε αυτήν την περίπτωση, θα ήταν ένα ανώτερο όριο για να το συνοδεύει - δηλαδή, μια απόδειξη ότι δεν θα μπορούσε να υπάρξει σύστημα στο οποίο ο προσδιορισμός της προσβασιμότητας ήταν ακόμη πιο δύσκολος. Αλλά κανείς δεν ήξερε πώς να το αποδείξει αυτό. Ο επιστήμονας υπολογιστών Ernst Mayr ήρθε πιο κοντά όταν εκείνος αποδείχθηκε το 1981 ότι είναι πάντα δυνατό, καταρχήν, να προσδιοριστεί η προσβασιμότητα σε οποιοδήποτε σύστημα πρόσθεσης διανυσμάτων. Αλλά η απόδειξή του δεν έθεσε κανένα ποσοτικό ανώτερο όριο για το πόσο δύσκολο θα μπορούσε να είναι το πρόβλημα. Υπήρχε ένα πάτωμα, αλλά δεν φαινόταν οροφή.

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

Το 2015 οι επιστήμονες πληροφορικής Jérôme Leroux και Sylvain Schmitz τελικά καθιερώθηκε ένα ποσοτικό άνω όριο — ένα τόσο υψηλό που οι ερευνητές υπέθεσαν ότι ήταν απλώς ένα πρώτο βήμα που θα μπορούσε να ωθηθεί προς τα κάτω για να συναντήσει το κάτω όριο του Lipton.

Αλλά δεν έγινε αυτό. Το 2019, οι ερευνητές ανακάλυψαν ένα χαμηλότερο όριο πολύ υψηλότερο από αυτό του Lipton, ανατρέποντας δεκαετίες συμβατικής σοφίας. Το πρόβλημα προσβασιμότητας του VAS ήταν πολύ πιο περίπλοκο από ό,τι περίμενε κανείς.

Ένας Πύργος Δυνάμεων

Το συγκλονιστικό αποτέλεσμα του 2019 προήλθε από αποτυχία. Το 2018, ο Czerwiński διέψευσε μια εικασία, των Leroux και Filip Mazowiecki, ένας επιστήμονας υπολογιστών τώρα στο Πανεπιστήμιο της Βαρσοβίας, που θα βοηθούσε στην επίτευξη προόδου σε ένα σχετικό πρόβλημα. Σε επόμενες συζητήσεις, οι ερευνητές χτύπησαν έναν πολλά υποσχόμενο νέο τρόπο για την κατασκευή εξαιρετικά πολύπλοκων συστημάτων προσθήκης διανυσμάτων, που θα μπορούσε να συνεπάγεται ένα νέο κατώτερο όριο στο πρόβλημα προσβασιμότητας του VAS, όπου η πρόοδος είχε σταματήσει για τόσο μεγάλο χρονικό διάστημα.

«Όλα συνδέονται στο μυαλό μου με την προσβασιμότητα του VAS», θυμάται ο Τσερβίνσκι. Κατά τη διάρκεια ενός εξαμήνου με μικρό διδακτικό φόρτο, αποφάσισε να επικεντρωθεί αποκλειστικά σε αυτό το πρόβλημα, μαζί με τον Leroux, τον Mazowiecki και δύο άλλους ερευνητές — Σλαβομίρ Λασότα του Πανεπιστημίου της Βαρσοβίας και Ράνκο Λάζιτς του Πανεπιστημίου του Warwick.

Μετά από λίγους μήνες, οι προσπάθειές τους απέδωσαν καρπούς. Czerwiński και οι συνάδελφοί του κατέδειξε ότι θα μπορούσαν να κατασκευάσουν συστήματα πρόσθεσης διανυσμάτων στα οποία η συντομότερη διαδρομή μεταξύ δύο καταστάσεων σχετιζόταν με το μέγεθος του συστήματος με μια μαθηματική πράξη που ονομάζεται τετροποίηση που κάνει ακόμη και την εφιαλτική διπλή εκθετική ανάπτυξη να φαίνεται ήμερη.

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

Είναι δύσκολο να περιγράψεις πόσο γρήγορα η τετραλογία ξεφεύγει από τον έλεγχο: $latex 2 uparrowuparrow 3$ ή $latex 2^{2^2}$, είναι 16, $latex 2 uparrowuparrow 4$ είναι λίγο πάνω από 65,000 και $latex 2 uparrowuparrow 5$ είναι ένας αριθμός με σχεδόν 20,000 ψηφία. Είναι φυσικά αδύνατο να γράψετε όλα τα ψηφία του $latex 2 uparrowuparrow 6$ — μια υποχρέωση του να ζεις σε ένα τόσο μικρό σύμπαν.

Στο ορόσημο αποτέλεσμά τους, ο Czerwiński και οι συνεργάτες του απέδειξαν ότι υπάρχουν συστήματα προσθήκης διανυσμάτων μεγέθους n όπου ο καλύτερος τρόπος για να προσδιορίσετε την προσβασιμότητα είναι να χαρτογραφήσετε μια διαδρομή που περιλαμβάνει περισσότερες από μεταβάσεις $latex 2 uparrowuparrow n$, υπονοώντας ένα νέο κατώτερο όριο που έκανε νανά το Lipton. Όμως, όσο περιστροφική κι αν είναι η τετραλογία, δεν ήταν ακόμα η τελευταία λέξη για την πολυπλοκότητα του προβλήματος.

To Quinquagintillion and Beyond 

Μόλις λίγους μήνες μετά το συγκλονιστικό νέο κατώτερο όριο για την πολυπλοκότητα της προσβασιμότητας του VAS, οι Leroux και Schmitz έσπρωξε προς τα κάτω το ανώτατο όριο που είχαν καθιερώσει τρία χρόνια νωρίτερα, αλλά δεν έφτασαν μέχρι την τετραλογία. Αντίθετα, απέδειξαν ότι η πολυπλοκότητα του προβλήματος της προσβασιμότητας δεν μπορεί να αναπτυχθεί γρηγορότερα από ένα μαθηματικό τέρας που ονομάζεται συνάρτηση Ackermann.

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

Η συνάρτηση Ackermann, που συμβολίζεται $latex A(n)$, είναι αυτό που λαμβάνετε όταν ανεβαίνετε ένα βήμα προς τα πάνω σε αυτήν την κλίμακα πράξεων με κάθε στάση στην αριθμητική γραμμή: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ και ούτω καθεξής. Ο αριθμός των ψηφίων στο $latex A(4)$ είναι από μόνος του ένας κολοσσιαίος αριθμός περίπου ίσος με 1 quinquagintillion — αυτό είναι το περίεργο και σπάνια απαραίτητο όνομα για ένα 1 ακολουθούμενο από 153 μηδενικά. «Μην ανησυχείτε για τον Άκερμαν των 5», συμβουλεύτηκε Χαβιέ Εσπάρζα, επιστήμονας υπολογιστών στο Τεχνικό Πανεπιστήμιο του Μονάχου.

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

Η τελική ανακάλυψη ήρθε το 2021, ενώ ο Czerwiński συμβούλευε έναν δευτεροετή φοιτητή που ονομαζόταν Łukasz Orlikowski. Ανέθεσε στον Ορλικόφσκι μια απλή παραλλαγή του προβλήματος για να τον φέρει σε ταχύτητα και η δουλειά του Ορλικόφσκι βοήθησε τους δυο τους να αναπτύξουν μια νέα τεχνική που εφαρμόστηκε επίσης στο γενικό πρόβλημα προσβασιμότητας. Αυτό τους επέτρεψε σηκώστε το κάτω όριο ουσιαστικά — μέχρι το άνω όριο του Leroux και του Schmitz Ackermann. Δουλεύοντας ανεξάρτητα, ο Leroux απέκτησε ισοδύναμο αποτέλεσμα περίπου την ίδια ώρα.

Τέλος, οι ερευνητές είχαν εντοπίσει την πραγματική πολυπλοκότητα του προβλήματος προσβασιμότητας. Το κάτω όριο των Czerwiński, Orlikowski και Leroux έδειξαν ότι υπάρχει μια ακολουθία προοδευτικά μεγαλύτερων συστημάτων πρόσθεσης διανυσμάτων στα οποία η συντομότερη διαδρομή μεταξύ δύο καταστάσεων αυξάνεται ανάλογα με τη συνάρτηση Ackermann. Το άνω φράγμα των Leroux και Schmitz έδειξε ότι το πρόβλημα προσβασιμότητας δεν μπορεί να γίνει πιο περίπλοκο από αυτό — λίγη παρηγοριά σε όποιον ελπίζει σε μια αλάνθαστη πρακτική διαδικασία για την επίλυσή του. Είναι μια εντυπωσιακή απεικόνιση του πόσο λεπτή μπορεί να είναι φαινομενικά απλά υπολογιστικά προβλήματα.

Ποτέ Τελειωμένο

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

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

«Κατά κάποιο τρόπο, είναι απλώς ντροπιαστικό για εμάς», είπε ο Mazowiecki.

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

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

Quanta διεξάγει μια σειρά από έρευνες για την καλύτερη εξυπηρέτηση του κοινού μας. Πάρτε το δικό μας έρευνα αναγνωστών επιστήμης υπολογιστών και θα μπείτε για να κερδίσετε δωρεάν Quanta εμπορεύματα.