Back to search

National and Kapodistrian University of Athens

Η Πολυωνυμική Ιεραρχία Συμβουλής και το Θεώρημα του Dinneen

Abstract

dc:description

H παρούσα διπλωματική εργασία ξεκίνησε και επεκτάθηκε με αφορμή και γνώμονα ένα θεώρημα του Dinneen, το οποίο αποτελεί μέρος της μελέτης του ρυθμού αυξησης του πληθάριθμου του συνόλου παρεμποδίσεων οικογενειών γραφημάτων, κλειστών ως προς ελάσσονα, τα οποία βασίζονται σε παραμετρικά προβλήματα. Επιπλέον συνδυάζει διαφο- ρετικούς τομείς των μαθηματικών, μιας και συσχετίζει την πολυπλοκότητα των προαναφερθέντων προβλημάτων, με την Πολυωνυμική Ιεραρχία και την κατάρρευση αυτής. Ο βασικός μας στόχος είναι η σύνοψη του συνόλου των μαθηματικών εννοιών και κεφαλαίων των μαθηματικών, πάνω στα οποία βασίζεται το θεώρημα αλλά και η περαιτέρω παρουσίαση και ανάλυση κάποιων θεωρημάτων και προτάσεων, που σχετίζονται άμεσα με αυτό, και αποτελούν εξεζητημένα θέματα της Υπολογιστικής Πολυπλοκότητας. Τα τελευταία, κυρίως, συνδέουν την κατάρρευση της Πολυωνυμικής Ιεραρχίας Συμβουλής με την κατάρρεση της Πολυωνυμικής Ιεραρχίας. Για να γίνουν σαφή όμως τα παραπάνω, απαιτείται η γνώση των Πολυωνυμικών Ιεραρχιών, της Kυκλωματικής Πολυπλοκότητας και πώς αυτή σχετίζεται με την κλασική Πολυπλοκότητα. Ο θεμέλιος λίθος και το βασικό εργαλείο για να αναπτυχθούν οι παραπάνω έννοιες αποτελούν οι Μηχανές Turing, που παρουσιάζονται στην αρχή. Ουσιαστικά δηλαδή η συλλογιστική πορεία της παρουσίασης είναι αντίστροφη του σχεδιασμού. Αυτό γίνεται χάρην ευκολίας της ανάγνωσης και καταγραφής, αλλά και για να παρουσιαστούν οι έννοιες με την φυσική τους σειρά.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Μελιανός Μιχαήλ
  • Melianos Michail

Subjects

dc:subject × 2

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:3227714

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Μελιανός Μιχαήλ; Melianos Michail. Η Πολυωνυμική Ιεραρχία Συμβουλής και το Θεώρημα του Dinneen. 2022. https://pergamos.lib.uoa.gr/uoa/dl/object/3227714