Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14101
Title: Ισομορφισμός Κλάσεων Και Κλάσεις Πολυπλοκότητας
Authors: Τζάννες Αλέξανδρος
Ζάχος Ευστάθιος
Keywords: ισομορφισμός
αυτομορφισμός
γράφος
δομική πολυπλοκότητα
πιθανοτικός
πολυωνυμική ιεραρχία
τελεστές
ποσοδείκτες
διαδραστικές αποδείξεις
μηδενική γνώση
arthur-merlin
παίγνια
lowness.
Issue Date: 23-Jul-2004
Abstract: Ο Ισομορφισμός Γράφων (GI) είναι ένα από τα ελάχιστα προβλήματα που αν και ανήκουν στην κλάση NP δεν είναι γνωστό αν ανήκουν στο P ή αν είναι NP-Complete (ή αν ισχύει κάτι άλλο γι'αυτό). Πολλές παραλλαγές του προβλήματος έχουν μελετηθεί και έχουν βρεθεί να ανήκουν στο P με αποκορύφωμα την περίπτωση του ισομορφισμού επίπεδων γράφων για το οποίο μάλιστα βρέθηκε αλγόριθμος που εκτελείται σε γραμμικό χρόνο. Υπάρχουν πολλά στοιχεία τα οποία συνηγορούν στο ότι το GI δεν είναι NP-Complete, αλλά παρόλα αυτά παραμένει αρκετά "μακρυά" από το P καθώς δεν είναι καν γνωστό αν ανήκει στο co-NP. Ένα πρόβλημα το οποίο μέχρι πριν μερικά χρόνια (2002) είχε το ίδιο status με το GI είναι το primality, το πρόβλημα απόφασης αν ένας ακέραιος είναι πρώτος. Για το primality όμως η εικασία ήταν εδώ και πολλά χρόνια ότι ανήκει στο P καθώς είχε αποδειχθεί ότι ήταν στο NP τομή co-NP και μάλιστα στο ZPP. Μέσα από αυτή τη διπλοματική εργασία, στόχος μου είναι να προσεγγίσω τη θεωρία πολυπλοκότητας μέσω ενός ανοιχτού προβλήματος (του GI) έτσι ώστε φανούν και κάποιες μεθοδολογίες αντιμετώπισης ανοιχτών προβλημάτων.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14101
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2004-0143.ps1.3 MBPostscriptView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.