Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2022-11-01
Συγγραφέας:
ΒΑΣΙΛΑΚΗΣ ΒΑΣΙΛΕΙΟΣ
Στοιχεία επιβλεπόντων καθηγητών:
ΑΡΧΟΝΤΙΑ ΓΙΑΝΝΟΠΟΥΛΟΥ, ΕΠΙΚΟΥΡΗ ΚΑΘΗΓΗΤΡΙΑ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ ΚΑΙ ΤΗΛΕΠΙΚΟΙΝΩΝΙΩΝ, ΕΚΠΑ
Πρωτότυπος Τίτλος:
Consequences of Polynomial Hierarchy in Parameterized Complexity: Tight Lower Bounds
Γλώσσες εργασίας:
Ελληνικά
Αγγλικά
Μεταφρασμένος τίτλος:
Συνέπειες της Πολυωνυμικής Ιεραρχίας στην Παραμετρική Πολυπλοκότητα: Σφιχτά Κάτω Φράγματα
Περίληψη:
Παρουσιάζεται και ορίζεται ένα αφηρημένο μοντέλο υπολογισμού που συνίσταται στην επικοινωνία μεταξύ δύο παιχτών, βασιζόμενοι σε κάποιο προκαθορισμένο πρωτόκολλο επικοινωνίας, με σκοπό την αναγνώριση μιας γλώσσας. Με κάθε πρωτόκολλο, ορίζεται και ποσοτικοποιείται ένα κόστος, και σκοπός μας είναι η ελαχιστοποίηση του κόστους ως προς όλα τα πρωτόκολλα. Προς αυτήν την κατεύθυνση, παρουσιάζονται τετριμμένα πρωτόκολλα για τα NP-πλήρη προβλήματα των d-SAT και d-Vertex-Cover. Αυτά τα τετριμμένα πρωτόκολλα αποδεικνύονται και βέλτιστου κόστους, υπό την υπόθεση ότι η πολυωνυμική ιεραρχία δεν καταρρέει. Αυτό το γεγονός έχει ενδιαφέρουσες επιπτώσεις σε τομείς της Παραμετρικής Πολυπλοκότητας αυτών των προβλημάτων και συγκεκριμένα στην αραιοποίηση, πυρηνοποίηση και συμπίεση, οι οποίες και παρουσιάζονται ως πορίσματα των κεντρικών αποτελεσμάτων.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
Αφηρημένα Μοντέλα Υπολογισμού, Κυκλωματική Πολυπλοκότητα, Πολυωνυμική Αναγωγή, Πολυωνυμική Ιεραρχία, Πρωτόκολλο Επικοινωνίας
Αρ. σελίδων ευρετηρίου:
3
Αρ. βιβλιογραφικών αναφορών:
11
