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

Το αποτέλεσμα θα μπορούσε να παράσχει μια βαθύτερη κατανόηση της φύσης της πληροφορικής και "θα μπορούσε να είναι για τη θεωρητική επιστήμη των υπολογιστών το αποτέλεσμα της δεκαετίας", σύμφωνα με τον Scott Aaronson του Massachusetts Institute of Technology.

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

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

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

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

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

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

Το μυστήριο είναι εάν αυτές οι δύο κλάσεις προβλημάτων , P και NP, είναι στην πραγματικότητα το ίδιο. Πιστεύεται ότι δεν είναι, γιατί τα προβλήματα Ρ είναι "εύκολα" και τα NP-complete είναι "σκληρά", αλλά κανείς δεν είναι σε θέση να το αποδείξει παρά τις δεκαετίες έρευνας - η απάντηση είναι αξίας 1 .000.000 $ .

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

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

"Οι άνθρωποι έχουν ξοδέψει τόσο πολύ χρόνο μελετώντας το πρόβλημα με ελάχιστη πρόοδο αφού οι θεωρητικοί το αποκαλούν το γράφημα ισομορφισμός ως ασθένεια", λέει ο Ryan Williams του Πανεπιστημίου του Στάνφορντ. "Μια σημαντική ανακάλυψη είναι επομένως μια μεγάλη υπόθεση,  δεν είναι ακριβώς η ανακάλυψη των  σωματιδίων και  το μποζόνιο Higgs, αλλά κάπου κοντά. 

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

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

"Δείχνει μια δύναμη των αλγορίθμων που δεν ξέραμε πριν," λέει ο Williams. "Με αυτή την έννοια, κατατάσσεται στα ίδια ζητήματα που αντιμετωπίζουμε όταν μιλάμε για πράγματα όπως το P έναντι NP".

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

Αναφορές από την ομιλία του χθες δείχνουν ότι η μέθοδος του László Babai περιλαμβάνει διαίρεση ενός γραφήματος σε διαφορετικά μέρη και την επίλυσή τους ξεχωριστά. Ορισμένες από αυτά τα  υπο-γραφήματα, γνωστά ως Johnson γραφήματα, είναι ιδιαίτερα δύσκολο να αναλυθούν.

Για την αντιμετώπιση αυτών , δανείζεται έννοιες από μια σημαντική εργασία σε άλλο τομέα των μαθηματικών που ονομάζεται Ομαδική Θεωρία, γνωστή ως  Κατάταξη Πεπερασμένων Απλών Ομάδων. Η απόδειξη αυτού είναι γνωστή από μόνη της για το τρέξιμο του αλγορίθμου σε δεκάδες χιλιάδες σελίδες. "Ακούγεται σαν ο Babai  έχει δημιουργήσει ένα τέρας ενός αλγορίθμου," λέει ο Williams.