Δύο γραφήματα λέγονται ισομορφικά αν έχουν την ίδια δομή, δηλαδή αν υπάρχει αντιστοιχία μεταξύ των κορυφών τους που διατηρεί τις συνδέσεις (ακμές). Με άλλα λόγια, τα γραφήματα είναι ουσιαστικά τα ίδια, ακόμα κι αν οι κορυφές έχουν διαφορετική ονομασία ή το σχέδιο τους είναι διαφορετικό.
Ο έλεγχος αν δύο γραφήματα είναι ισομορφικά — γνωστός ως πρόβλημα ισομορφισμού γραφημάτων (Graph Isomorphism Problem) — αποτελεί ένα από τα πιο γνωστά ανοιχτά προβλήματα στην Υπολογιστική Πολυπλοκότητα.
Η ακριβής θέση του δεν έχει ακόμα καθοριστεί: δεν έχει αποδειχθεί ότι είναι NP-complete, αλλά ούτε και ότι ανήκει στην τάξη P (προβλήματα που λύνονται σε πολυωνυμικό χρόνο). Εικάζεται ότι βρίσκεται «ενδιάμεσα».
Το 2015, ο László Babai ανακοίνωσε έναν ημισχεδόν-πολυωνυμικό αλγόριθμο για το πρόβλημα, με χρόνο εκτέλεσης $exp((logn)^{O(1))}$, βελτιώνοντας σημαντικά τις προηγούμενες προσεγγίσεις. Ωστόσο, η πλήρης κατάταξη του προβλήματος παραμένει άγνωστη.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου