Counting below #P: Classes, problems and Descriptive Complexity

Διπλωματική Εργασία uoadl:1320955 225 Αναγνώσεις

Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2016-09-23
Έτος εκπόνησης:
2016
Συγγραφέας:
Χαλκή Αγγελική
Στοιχεία επιβλεπόντων καθηγητών:
Στάθης Ζάχος Καθηγητής, Άρης Παγουρτζής Αναπλ. Καθηγητής (Επιβλέπων), Δημήτρης Φωτάκης Επίκ. Καθηγητής
Πρωτότυπος Τίτλος:
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
Αριθμός σελίδων:
80