{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:3227714"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:3227714","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Η Πολυωνυμική Ιεραρχία Συμβουλής και το Θεώρημα του Dinneen","abstract":"H παρούσα διπλωματική εργασία ξεκίνησε και επεκτάθηκε με αφορμή και γνώμονα ένα θεώρημα του Dinneen, το οποίο αποτελεί μέρος της μελέτης του ρυθμού αυξησης του πληθάριθμου του συνόλου παρεμποδίσεων οικογενειών γραφημάτων, κλειστών ως προς ελάσσονα, τα οποία βασίζονται σε παραμετρικά προβλήματα. Επιπλέον συνδυάζει διαφο- ρετικούς τομείς των μαθηματικών, μιας και συσχετίζει την πολυπλοκότητα των προαναφερθέντων προβλημάτων, με την Πολυωνυμική Ιεραρχία και την κατάρρευση αυτής. Ο βασικός μας στόχος είναι η σύνοψη του συνόλου των μαθηματικών εννοιών και κεφαλαίων των μαθηματικών, πάνω στα οποία βασίζεται το θεώρημα αλλά και η περαιτέρω παρουσίαση και ανάλυση κάποιων θεωρημάτων και προτάσεων, που σχετίζονται άμεσα με αυτό, και αποτελούν εξεζητημένα θέματα της Υπολογιστικής Πολυπλοκότητας. Τα τελευταία, κυρίως, συνδέουν την κατάρρευση της Πολυωνυμικής Ιεραρχίας Συμβουλής με την κατάρρεση της Πολυωνυμικής Ιεραρχίας. Για να γίνουν σαφή όμως τα παραπάνω, απαιτείται η γνώση των Πολυωνυμικών Ιεραρχιών, της Kυκλωματικής Πολυπλοκότητας και πώς αυτή σχετίζεται με την κλασική Πολυπλοκότητα. Ο θεμέλιος λίθος και το βασικό εργαλείο για να αναπτυχθούν οι παραπάνω έννοιες αποτελούν οι Μηχανές Turing, που παρουσιάζονται στην αρχή. Ουσιαστικά δηλαδή η συλλογιστική πορεία της παρουσίασης είναι αντίστροφη του σχεδιασμού. Αυτό γίνεται χάρην ευκολίας της ανάγνωσης και καταγραφής, αλλά και για να παρουσιαστούν οι έννοιες με την φυσική τους σειρά.","abstract_html":"H παρούσα διπλωματική εργασία ξεκίνησε και επεκτάθηκε με αφορμή και γνώμονα ένα θεώρημα του Dinneen, το οποίο αποτελεί μέρος της μελέτης του ρυθμού αυξησης του πληθάριθμου του συνόλου παρεμποδίσεων οικογενειών γραφημάτων, κλειστών ως προς ελάσσονα, τα οποία βασίζονται σε παραμετρικά προβλήματα. Επιπλέον συνδυάζει διαφο- ρετικούς τομείς των μαθηματικών, μιας και συσχετίζει την πολυπλοκότητα των προαναφερθέντων προβλημάτων, με την Πολυωνυμική Ιεραρχία και την κατάρρευση αυτής. Ο βασικός μας στόχος είναι η σύνοψη του συνόλου των μαθηματικών εννοιών και κεφαλαίων των μαθηματικών, πάνω στα οποία βασίζεται το θεώρημα αλλά και η περαιτέρω παρουσίαση και ανάλυση κάποιων θεωρημάτων και προτάσεων, που σχετίζονται άμεσα με αυτό, και αποτελούν εξεζητημένα θέματα της Υπολογιστικής Πολυπλοκότητας. Τα τελευταία, κυρίως, συνδέουν την κατάρρευση της Πολυωνυμικής Ιεραρχίας Συμβουλής με την κατάρρεση της Πολυωνυμικής Ιεραρχίας. Για να γίνουν σαφή όμως τα παραπάνω, απαιτείται η γνώση των Πολυωνυμικών Ιεραρχιών, της Kυκλωματικής Πολυπλοκότητας και πώς αυτή σχετίζεται με την κλασική Πολυπλοκότητα. Ο θεμέλιος λίθος και το βασικό εργαλείο για να αναπτυχθούν οι παραπάνω έννοιες αποτελούν οι Μηχανές Turing, που παρουσιάζονται στην αρχή. Ουσιαστικά δηλαδή η συλλογιστική πορεία της παρουσίασης είναι αντίστροφη του σχεδιασμού. Αυτό γίνεται χάρην ευκολίας της ανάγνωσης και καταγραφής, αλλά και για να παρουσιαστούν οι έννοιες με την φυσική τους σειρά.","abstract_has_math":false,"creators":["Μελιανός Μιχαήλ","Melianos Michail"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022","date_published":"2022","updated_at":"2026-11-19T05:47:22Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3227714"],"render_values":[{"text":"uoadl:3227714","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3227714","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3227714","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A3227714","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Μελιανός Μιχαήλ","Melianos Michail"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3227714","https://pergamos.lib.uoa.gr/uoa/dl/object/3227714"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["H παρούσα διπλωματική εργασία ξεκίνησε και επεκτάθηκε με αφορμή και γνώμονα ένα θεώρημα του Dinneen, το οποίο αποτελεί μέρος της μελέτης του ρυθμού αυξησης του πληθάριθμου του συνόλου παρεμποδίσεων οικογενειών γραφημάτων, κλειστών ως προς ελάσσονα, τα οποία βασίζονται σε παραμετρικά προβλήματα. Επιπλέον συνδυάζει διαφο- ρετικούς τομείς των μαθηματικών, μιας και συσχετίζει την πολυπλοκότητα των προαναφερθέντων προβλημάτων, με την Πολυωνυμική Ιεραρχία και την κατάρρευση αυτής. Ο βασικός μας στόχος είναι η σύνοψη του συνόλου των μαθηματικών εννοιών και κεφαλαίων των μαθηματικών, πάνω στα οποία βασίζεται το θεώρημα αλλά και η περαιτέρω παρουσίαση και ανάλυση κάποιων θεωρημάτων και προτάσεων, που σχετίζονται άμεσα με αυτό, και αποτελούν εξεζητημένα θέματα της Υπολογιστικής Πολυπλοκότητας. Τα τελευταία, κυρίως, συνδέουν την κατάρρευση της Πολυωνυμικής Ιεραρχίας Συμβουλής με την κατάρρεση της Πολυωνυμικής Ιεραρχίας. Για να γίνουν σαφή όμως τα παραπάνω, απαιτείται η γνώση των Πολυωνυμικών Ιεραρχιών, της Kυκλωματικής Πολυπλοκότητας και πώς αυτή σχετίζεται με την κλασική Πολυπλοκότητα. Ο θεμέλιος λίθος και το βασικό εργαλείο για να αναπτυχθούν οι παραπάνω έννοιες αποτελούν οι Μηχανές Turing, που παρουσιάζονται στην αρχή. Ουσιαστικά δηλαδή η συλλογιστική πορεία της παρουσίασης είναι αντίστροφη του σχεδιασμού. Αυτό γίνεται χάρην ευκολίας της ανάγνωσης και καταγραφής, αλλά και για να παρουσιαστούν οι έννοιες με την φυσική τους σειρά.","The present dissertation began and expanded on the occasion and in the light by one of Dinneen's theorems, which, is part of the study of the growth rate of the number obstructions for families of graphs, which closed under minors, are based on parameterized problems. Furthermore, combines different reticular files of mathematics since it correlates the complexity of the above alleged problems, with the Polynomial Hierarchy and its collapse. Our main goal is to summarize all the mathematical concepts and chapters of mathematics on which the theorem is based, as well as the further presentation and analysis of some theorems and propositions that are directly related to it and are sophisticated topics of Computational Complexity. The latter, in patricular, links the collapse of the Polynomial Hierarchy of Advice with the collapse of the Polynomial Hierarchy. However, in order to make the above clear, knowledge of Polynomial Hierarchies, Circuit Complexity and how it relates to classical Complexity is required. The foundatiton stone and the basic tool for developing the above concepts are the Turing Machines, presented at the beginning. Essentially the reasoning course of the presentation is the inverse of the design. This is done for the sake of ease of reading and recording dut in order to also present the concepts in their natural order."]},{"key":"dc:title","label":"Title","values":["Η Πολυωνυμική Ιεραρχία Συμβουλής και το Θεώρημα του Dinneen"]}]}],"canonical_facts":{"dc:creator":["Μελιανός Μιχαήλ","Melianos Michail"],"dc:date":["2022"],"dc:description":["H παρούσα διπλωματική εργασία ξεκίνησε και επεκτάθηκε με αφορμή και γνώμονα ένα θεώρημα του Dinneen, το οποίο αποτελεί μέρος της μελέτης του ρυθμού αυξησης του πληθάριθμου του συνόλου παρεμποδίσεων οικογενειών γραφημάτων, κλειστών ως προς ελάσσονα, τα οποία βασίζονται σε παραμετρικά προβλήματα. Επιπλέον συνδυάζει διαφο- ρετικούς τομείς των μαθηματικών, μιας και συσχετίζει την πολυπλοκότητα των προαναφερθέντων προβλημάτων, με την Πολυωνυμική Ιεραρχία και την κατάρρευση αυτής. Ο βασικός μας στόχος είναι η σύνοψη του συνόλου των μαθηματικών εννοιών και κεφαλαίων των μαθηματικών, πάνω στα οποία βασίζεται το θεώρημα αλλά και η περαιτέρω παρουσίαση και ανάλυση κάποιων θεωρημάτων και προτάσεων, που σχετίζονται άμεσα με αυτό, και αποτελούν εξεζητημένα θέματα της Υπολογιστικής Πολυπλοκότητας. Τα τελευταία, κυρίως, συνδέουν την κατάρρευση της Πολυωνυμικής Ιεραρχίας Συμβουλής με την κατάρρεση της Πολυωνυμικής Ιεραρχίας. Για να γίνουν σαφή όμως τα παραπάνω, απαιτείται η γνώση των Πολυωνυμικών Ιεραρχιών, της Kυκλωματικής Πολυπλοκότητας και πώς αυτή σχετίζεται με την κλασική Πολυπλοκότητα. Ο θεμέλιος λίθος και το βασικό εργαλείο για να αναπτυχθούν οι παραπάνω έννοιες αποτελούν οι Μηχανές Turing, που παρουσιάζονται στην αρχή. Ουσιαστικά δηλαδή η συλλογιστική πορεία της παρουσίασης είναι αντίστροφη του σχεδιασμού. Αυτό γίνεται χάρην ευκολίας της ανάγνωσης και καταγραφής, αλλά και για να παρουσιαστούν οι έννοιες με την φυσική τους σειρά.","The present dissertation began and expanded on the occasion and in the light by one of Dinneen's theorems, which, is part of the study of the growth rate of the number obstructions for families of graphs, which closed under minors, are based on parameterized problems. Furthermore, combines different reticular files of mathematics since it correlates the complexity of the above alleged problems, with the Polynomial Hierarchy and its collapse. Our main goal is to summarize all the mathematical concepts and chapters of mathematics on which the theorem is based, as well as the further presentation and analysis of some theorems and propositions that are directly related to it and are sophisticated topics of Computational Complexity. The latter, in patricular, links the collapse of the Polynomial Hierarchy of Advice with the collapse of the Polynomial Hierarchy. However, in order to make the above clear, knowledge of Polynomial Hierarchies, Circuit Complexity and how it relates to classical Complexity is required. The foundatiton stone and the basic tool for developing the above concepts are the Turing Machines, presented at the beginning. Essentially the reasoning course of the presentation is the inverse of the design. This is done for the sake of ease of reading and recording dut in order to also present the concepts in their natural order."],"dc:identifier":["uoadl:3227714","https://pergamos.lib.uoa.gr/uoa/dl/object/3227714"],"dc:language":["Ελληνικά","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Η Πολυωνυμική Ιεραρχία Συμβουλής και το Θεώρημα του Dinneen"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:47:22Z"}