National and Kapodistrian University of Athens
Counting below #P: Classes, problems and Descriptive Complexity
Abstract
dc:descriptionΣτην παρούσα διπλωματική, μελετάμε μετρητικές κλάσεις οι οποίες περιέχονται στη #P. Μία προσέγγιση, η πιο διαδεδομένη στη Θεωρία Υπολογιστικής Πολυπλοκότητας, είναι ο ορισμός κλάσεων με βάση τη μηχανή Turing. Κλάσεις όπως οι #L, span-L και TotP, #PE προκύπτουν θέτοντας περιορισμούς στους υπολογιστικούς πόρους που διαθέτει μια μηχανή Turing. Μία δεύτερη προσέγγιση είναι αυτή της Περιγραφικής Πολυπλοκότητας. Μέσω αυτής τα μετρητικά προβλήματα εκφράζονται στη γλώσσα κάποιας λογικής, και μία κλάση πολυπλοκότητας ορίζεται με βάση τη λογική στην οποία εκφράζονται τα προβλήματά της. Κλάσεις όπως οι #FO, #RHΠ_1, #RHΣ_2 είναι ισοδύναμες με τη #P, την κλάση των AP-ισοδύναμων προβλημάτων με το #BIS, και με κάποια υποκλάση των προβλημάτων που επιδέχονται FPRAS αντίστοιχα. Ένας σπουδαίος στόχος για μια τέτοια μελέτη είναι η σύνδεση του αποδοτικού υπολογισμού, όσον αφορά τη μέτρηση λύσεων, με τις ήδη υπάρχουσες μετρητικές κλάσεις. Με τον όρο αποδοτική μέτρηση εννοούμε τη μέτρηση λύσεων σε πολυωνυμικό χρόνο ή με χρήση FPRAS. Επίσης διερευνώνται άλλες ενδιαφέρουσες ιδιότητες των υποκλάσεων της #P. Για παράδειγμα, εναλλακτικοί ορισμοί με βάση τη μέτρηση ορισμάτων σχέσεων, η υπολογιστική δυσκολία πλήρων προβλημάτων, τα οποία αποτυπώνουν τη δυσκολία της αντίστοιχης κλάσης. Στην ενότητα 3.5 ορίζουμε την κλάση TotL, και ερευνούμε κατά πόσο συμπεράσματα γνωστά για την TotP μπορούν να μεταφερθούν σε λογαριθμικού χώρου υπολογισμούς και να διατυπωθούν και γι'αυτή τη νέα κλάση.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Χαλκή Αγγελική
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1320955