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

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

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

Την τελευταία δεκαετία, υπήρξαν ορισμένα σημαντικά αποτελέσματα που αποδεικνύουν ότι οι υπολογιστές μπορούν να τα πάνε τουλάχιστον λίγο καλύτερα από αυτό. Ενα από τα μεγαλύτερα πρόσφατα αποτελέσματα στην επιστήμη των υπολογιστών ήταν ένας ταχύτερος αλγόριθμος για τον προσδιορισμό του πότε δύο γραφήματα είναι ίδια. Το έργο του 2015, από László Babai του Πανεπιστημίου του Σικάγο, έσπασε ένα σημαντικό φράγμα υπολογιστικής ταχύτητας αλλά έπεσε κάτω από ένα άλλο.

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

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

«Δεν γνωρίζουμε ένα τέτοιο θεώρημα, αλλά έχουμε λόγους να πιστεύουμε ότι κάτι τέτοιο πρέπει να ισχύει», είπε Τζος Γκρόχοου του Πανεπιστημίου του Κολοράντο, Boulder.

Σύγκριση συγκρίσεων

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

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

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

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

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

Ακολουθεί ένα απλό παράδειγμα δύο ομάδων, η καθεμία με δύο στοιχεία, που είναι ισόμορφα μεταξύ τους. Η πρώτη ομάδα αποτελείται από τους αριθμούς 0 και 1 και η δεύτερη ομάδα αποτελείται από τα γράμματα a και b. Και οι δύο ομάδες περιέχουν μια λειτουργία για το συνδυασμό των στοιχείων της ομάδας με συγκεκριμένο τρόπο, με τα αποτελέσματα που παρουσιάζονται στους παρακάτω πίνακες.

Οι ομάδες είναι ισόμορφες επειδή 0 ζεύγη με a, 1 ζευγάρια με b, και η δομική σχέση που παράγεται από το συνδυασμό στοιχείων είναι η ίδια και στις δύο ομάδες.

«Λέμε ότι δύο ομάδες είναι ισόμορφες αν είναι βασικά ισοδύναμες», είπε ο Sun.

Μη ισορροπημένη Πρόοδος

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

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

Θα περίμενε κανείς να πάρει περισσότερο χρόνο από έναν αλγόριθμο για να προσδιορίσει εάν οι ομάδες με περισσότερα στοιχεία είναι ισομορφικές. Μα πόσο χρόνο ακόμα; Θα πάρει διπλάσιο χρόνο; 5² μακρύτερα? 2⁵ μακρύτερα? Αυτές οι ερωτήσεις αντιστοιχούν σε σημαντικές ευρείες ταξινομήσεις αλγοριθμικής ταχύτητας: Μπορούν να εκτελεστούν σε γραμμικό χρόνο (που σημαίνει ότι σε αυτήν την περίπτωση χρειάζεται διπλάσιος χρόνος), πολυωνυμικός χρόνος (5² μεγαλύτερος) και εκθετικός χρόνος (2⁵ μακρύτερα).

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

«Τα περισσότερα είναι είτε τα πιο εύκολα είτε τα πιο δύσκολα [είδος ερώτησης], αλλά εξακολουθούν να υπάρχουν αρκετές εξαιρέσεις που είναι άγνωστες», είπε ο Sun. Ο γραφικός και ο ομαδικός ισομορφισμός είναι μεταξύ αυτών των εξαιρέσεων, κάτι που τα κάνει τόσο ελκυστικά στη μελέτη.

Στα 1970, Ρόμπερτ Ταριάν του Πανεπιστημίου του Πρίνστον συνειδητοποίησε ότι υπάρχει ένας αλγόριθμος που μπορεί να καθορίσει εάν οποιεσδήποτε δύο ομάδες είναι ισόμορφες με χρόνο εκτέλεσης $latex n^{{(log,n)}}$, όπου n είναι ο αριθμός των στοιχείων σε κάθε ομάδα. Αυτό ονομάζεται αλγόριθμος σχεδόν πολυωνυμικού χρόνου και στην ιεραρχία των χρόνων εκτέλεσης είναι καλύτερος από τον εκθετικό χρόνο (2ⁿ) αλλά χειρότερο από τον πολυωνυμικό χρόνο (n²). Αυτή είναι περίπου η ίδια ταχύτητα με τον αλγόριθμο ισομορφισμού γραφήματος του Babai, και εξακολουθεί να είναι το καλύτερο που μπορούμε να κάνουμε για ομάδες σχεδόν 50 χρόνια αργότερα.

"Αυτό σημαίνει περίπου ότι δεν υπάρχει πρόοδος εδώ και μισό αιώνα", είπε ο Sun.

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

"Όλα τα εργαλεία μας ήταν πολύ αργά εδώ και χρόνια και ήταν δύσκολο να εκμεταλλευτούμε όσα γνωρίζουμε για την άλγεβρα [των ομάδων]", είπε. James Wilson του Κρατικού Πανεπιστημίου του Κολοράντο.

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

«Με άλλα λόγια», είπε ο Sun, «προκειμένου να βελτιωθεί περαιτέρω ο ισομορφισμός του γραφήματος, ο ομαδικός ισομορφισμός είναι ένα μεγάλο εμπόδιο».

Ένα πρόβλημα που μεταμορφώθηκε

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

Το έργο του Sun περιέχει μερικές ιδέες που περιλαμβάνουν τη στόχευση ενός σημαντικού τύπου ομάδας και την εύρεση ενός έξυπνου τρόπου για να σπάσετε αυτές τις ομάδες σε κομμάτια προκειμένου να τις συγκρίνουν.

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

Ο Ήλιος ξεκίνησε αλλάζοντας τη ρύθμιση από ομάδες σε πίνακες, πίνακες αριθμών που χρησιμεύουν ως θεμελιώδη αντικείμενα στη γραμμική άλγεβρα. Αυτό ήταν δυνατό χάρη σε ένα θεώρημα από τη δεκαετία του 1930 που ονομάζεται αντιστοιχία Baer, ​​το οποίο μετατρέπει αυτήν την εκδοχή του ερωτήματος του ισομορφισμού ομάδας σε ένα απολύτως ανάλογο πρόβλημα σχετικά με τους πίνακες. Συγκεκριμένα, ο Sun εργάστηκε με χώρους μήτρας, οι οποίοι είναι συλλογές πινάκων με μια ειδική ιδιότητα: Ο (γραμμικός) συνδυασμός οποιωνδήποτε δύο πινάκων στο διάστημα ισούται με έναν άλλο πίνακα στο χώρο.

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

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

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

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

«Συμπληρώνω όλα τα πράγματα που μπορώ να πω γρήγορα ότι είναι περιοριστικά και τώρα μπορεί να επιστρέψω και να δοκιμάσω την καρδιά μου στα κουτιά που λείπουν», είπε ο Wilson. "Εάν έχετε περιορίσει το πεδίο εφαρμογής, τώρα είναι η κατάλληλη στιγμή να αλλάξετε ταχύτητα και να χρησιμοποιήσετε τον υπολογιστή για να αναζητήσετε τις σωστές τιμές."

Η ανακάλυψη του Ήλιου έδειχνε ότι είναι πάντα δυνατό να γίνει αυτή η διαίρεση για τους χώρους του πίνακα που αντιστοιχούν σε p-ομάδες κλάσης 2 και εκθέτη p. Στη συνέχεια απέδειξε ότι μετά από έναν τέτοιο διαχωρισμό, ένας συνδυασμός αλγοριθμικών τεχνικών καθιστά δυνατό τον προσδιορισμό του αν δύο κενά είναι ισόμορφα σε $latex n^{{(log,n)}^{5/6}}$ χρόνο, μια τιμή που είναι ελαφρώς χαμηλότερο από τη μέθοδο $latex n^{{(log,n)}}$ του Tarjan. (Και οι δύο αλγόριθμοι περιλαμβάνουν επίσης σταθερούς όρους, οι οποίοι δεν έχουν μεγάλη επίδραση στο χρόνο εκτέλεσης και τους οποίους παραλείψαμε για λόγους σαφήνειας.)

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

«Αν μπορείτε να το λύσετε p-Ομάδες, πιθανότατα μπορείτε να λύσετε το όλο θέμα», είπε ο Grochow. "Μπορεί."