Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Χαλκή Αγγελική. Counting below #P: Classes, problems and Descriptive Complexity. 2016. https://pergamos.lib.uoa.gr/uoa/dl/object/1320955