Ισομορφισμός Κλάσεων Και Κλάσεις Πολυπλοκότητας

Abstract

Ο Ισομορφισμός Γράφων (GI) είναι ένα από τα ελάχιστα προβλήματα που αν και ανήκουν στην κλάση NP δεν είναι γνωστό αν ανήκουν στο P ή αν είναι NP-Complete (ή αν ισχύει κάτι άλλο γι'αυτό). Πολλές παραλλαγές του προβλήματος έχουν μελετηθεί και έχουν βρεθεί να ανήκουν στο P με αποκορύφωμα την περίπτωση του ισομορφισμού επίπεδων γράφων για το οποίο μάλιστα βρέθηκε αλγόριθμος που εκτελείται σε γραμμικό χρόνο. Υπάρχουν πολλά στοιχεία τα οποία συνηγορούν στο ότι το GI δεν είναι NP-Complete, αλλά παρόλα αυτά παραμένει αρκετά "μακρυά" από το P καθώς δεν είναι καν γνωστό αν ανήκει στο co-NP. Ένα πρόβλημα το οποίο μέχρι πριν μερικά χρόνια (2002) είχε το ίδιο status με το GI είναι το primality, το πρόβλημα απόφασης αν ένας ακέραιος είναι πρώτος. Για το primality όμως η εικασία ήταν εδώ και πολλά χρόνια ότι ανήκει στο P καθώς είχε αποδειχθεί ότι ήταν στο NP τομή co-NP και μάλιστα στο ZPP. Μέσα από αυτή τη διπλοματική εργασία, στόχος μου είναι να προσεγγίσω τη θεωρία πολυπλοκότητας μέσω ενός ανοιχτού προβλήματος (του GI) έτσι ώστε φανούν και κάποιες μεθοδολογίες αντιμετώπισης ανοιχτών προβλημάτων.