National and Kapodistrian University of Athens
Η Πολυωνυμική Ιεραρχία Συμβουλής και το Θεώρημα του Dinneen
Abstract
dc:descriptionH παρούσα διπλωματική εργασία ξεκίνησε και επεκτάθηκε με αφορμή και γνώμονα ένα θεώρημα του Dinneen, το οποίο αποτελεί μέρος της μελέτης του ρυθμού αυξησης του πληθάριθμου του συνόλου παρεμποδίσεων οικογενειών γραφημάτων, κλειστών ως προς ελάσσονα, τα οποία βασίζονται σε παραμετρικά προβλήματα. Επιπλέον συνδυάζει διαφο- ρετικούς τομείς των μαθηματικών, μιας και συσχετίζει την πολυπλοκότητα των προαναφερθέντων προβλημάτων, με την Πολυωνυμική Ιεραρχία και την κατάρρευση αυτής. Ο βασικός μας στόχος είναι η σύνοψη του συνόλου των μαθηματικών εννοιών και κεφαλαίων των μαθηματικών, πάνω στα οποία βασίζεται το θεώρημα αλλά και η περαιτέρω παρουσίαση και ανάλυση κάποιων θεωρημάτων και προτάσεων, που σχετίζονται άμεσα με αυτό, και αποτελούν εξεζητημένα θέματα της Υπολογιστικής Πολυπλοκότητας. Τα τελευταία, κυρίως, συνδέουν την κατάρρευση της Πολυωνυμικής Ιεραρχίας Συμβουλής με την κατάρρεση της Πολυωνυμικής Ιεραρχίας. Για να γίνουν σαφή όμως τα παραπάνω, απαιτείται η γνώση των Πολυωνυμικών Ιεραρχιών, της Kυκλωματικής Πολυπλοκότητας και πώς αυτή σχετίζεται με την κλασική Πολυπλοκότητα. Ο θεμέλιος λίθος και το βασικό εργαλείο για να αναπτυχθούν οι παραπάνω έννοιες αποτελούν οι Μηχανές Turing, που παρουσιάζονται στην αρχή. Ουσιαστικά δηλαδή η συλλογιστική πορεία της παρουσίασης είναι αντίστροφη του σχεδιασμού. Αυτό γίνεται χάρην ευκολίας της ανάγνωσης και καταγραφής, αλλά και για να παρουσιαστούν οι έννοιες με την φυσική τους σειρά.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Μελιανός Μιχαήλ
- Melianos Michail
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:3227714