Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2016-09-23
Συγγραφέας:
Χαλκή Αγγελική
Στοιχεία επιβλεπόντων καθηγητών:
Στάθης Ζάχος Καθηγητής, Άρης Παγουρτζής Αναπλ. Καθηγητής (Επιβλέπων), Δημήτρης Φωτάκης Επίκ. Καθηγητής
Πρωτότυπος Τίτλος:
Counting below #P: Classes, problems and Descriptive Complexity
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Μέτρηση μέσα στη #P: Κλάσεις, προβλήματα και Περιγραφική Πολυπλοκότητα
Περίληψη:
Στην παρούσα διπλωματική, μελετάμε μετρητικές κλάσεις οι οποίες περιέχονται στη
#P.
Μία προσέγγιση, η πιο διαδεδομένη στη Θεωρία Υπολογιστικής Πολυπλοκότητας,
είναι ο ορισμός κλάσεων με βάση τη μηχανή Turing. Κλάσεις όπως οι #L, span-L
και TotP, #PE προκύπτουν θέτοντας περιορισμούς στους υπολογιστικούς πόρους που
διαθέτει μια μηχανή Turing.
Μία δεύτερη προσέγγιση είναι αυτή της Περιγραφικής Πολυπλοκότητας. Μέσω αυτής
τα μετρητικά προβλήματα εκφράζονται στη γλώσσα κάποιας λογικής, και μία κλάση
πολυπλοκότητας ορίζεται με βάση τη λογική στην οποία εκφράζονται τα προβλήματά
της. Κλάσεις όπως οι #FO, #RHΠ_1, #RHΣ_2 είναι ισοδύναμες με τη #P, την κλάση
των AP-ισοδύναμων προβλημάτων με το #BIS, και με κάποια υποκλάση των
προβλημάτων που επιδέχονται FPRAS αντίστοιχα.
Ένας σπουδαίος στόχος για μια τέτοια μελέτη είναι η σύνδεση του αποδοτικού
υπολογισμού, όσον αφορά τη μέτρηση λύσεων, με τις ήδη υπάρχουσες μετρητικές
κλάσεις. Με τον όρο αποδοτική μέτρηση εννοούμε τη μέτρηση λύσεων σε πολυωνυμικό
χρόνο ή με χρήση FPRAS.
Επίσης διερευνώνται άλλες ενδιαφέρουσες ιδιότητες των υποκλάσεων της #P. Για
παράδειγμα, εναλλακτικοί ορισμοί με βάση τη μέτρηση ορισμάτων σχέσεων, η
υπολογιστική δυσκολία πλήρων προβλημάτων, τα οποία αποτυπώνουν τη δυσκολία της
αντίστοιχης κλάσης. Στην ενότητα 3.5 ορίζουμε την κλάση TotL, και ερευνούμε
κατά πόσο συμπεράσματα γνωστά για την TotP μπορούν να μεταφερθούν σε
λογαριθμικού χώρου υπολογισμούς και να διατυπωθούν και γι'αυτή τη νέα κλάση.
Λέξεις-κλειδιά:
Υπολογιστική πολυπλοκότητα, Μετρητικές κλάσεις, Λογαριθμικός χώρος, Περιγραφική πολυπλοκότητα, span-L
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
58