{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320955"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320955","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Counting below #P: Classes, problems and Descriptive Complexity","abstract":"Στην παρούσα διπλωματική, μελετάμε μετρητικές κλάσεις οι οποίες περιέχονται στη #P. Μία προσέγγιση, η πιο διαδεδομένη στη Θεωρία Υπολογιστικής Πολυπλοκότητας, είναι ο ορισμός κλάσεων με βάση τη μηχανή Turing. Κλάσεις όπως οι #L, span-L και TotP, #PE προκύπτουν θέτοντας περιορισμούς στους υπολογιστικούς πόρους που διαθέτει μια μηχανή Turing. Μία δεύτερη προσέγγιση είναι αυτή της Περιγραφικής Πολυπλοκότητας. Μέσω αυτής τα μετρητικά προβλήματα εκφράζονται στη γλώσσα κάποιας λογικής, και μία κλάση πολυπλοκότητας ορίζεται με βάση τη λογική στην οποία εκφράζονται τα προβλήματά της. Κλάσεις όπως οι #FO, #RHΠ_1, #RHΣ_2 είναι ισοδύναμες με τη #P, την κλάση των AP-ισοδύναμων προβλημάτων με το #BIS, και με κάποια υποκλάση των προβλημάτων που επιδέχονται FPRAS αντίστοιχα. Ένας σπουδαίος στόχος για μια τέτοια μελέτη είναι η σύνδεση του αποδοτικού υπολογισμού, όσον αφορά τη μέτρηση λύσεων, με τις ήδη υπάρχουσες μετρητικές κλάσεις. Με τον όρο αποδοτική μέτρηση εννοούμε τη μέτρηση λύσεων σε πολυωνυμικό χρόνο ή με χρήση FPRAS. Επίσης διερευνώνται άλλες ενδιαφέρουσες ιδιότητες των υποκλάσεων της #P. Για παράδειγμα, εναλλακτικοί ορισμοί με βάση τη μέτρηση ορισμάτων σχέσεων, η υπολογιστική δυσκολία πλήρων προβλημάτων, τα οποία αποτυπώνουν τη δυσκολία της αντίστοιχης κλάσης. Στην ενότητα 3.5 ορίζουμε την κλάση TotL, και ερευνούμε κατά πόσο συμπεράσματα γνωστά για την TotP μπορούν να μεταφερθούν σε λογαριθμικού χώρου υπολογισμούς και να διατυπωθούν και γι'αυτή τη νέα κλάση.","abstract_html":"Στην παρούσα διπλωματική, μελετάμε μετρητικές κλάσεις οι οποίες περιέχονται στη #P. Μία προσέγγιση, η πιο διαδεδομένη στη Θεωρία Υπολογιστικής Πολυπλοκότητας, είναι ο ορισμός κλάσεων με βάση τη μηχανή Turing. Κλάσεις όπως οι #L, span-L και TotP, #PE προκύπτουν θέτοντας περιορισμούς στους υπολογιστικούς πόρους που διαθέτει μια μηχανή Turing. Μία δεύτερη προσέγγιση είναι αυτή της Περιγραφικής Πολυπλοκότητας. Μέσω αυτής τα μετρητικά προβλήματα εκφράζονται στη γλώσσα κάποιας λογικής, και μία κλάση πολυπλοκότητας ορίζεται με βάση τη λογική στην οποία εκφράζονται τα προβλήματά της. Κλάσεις όπως οι #FO, #RHΠ_1, #RHΣ_2 είναι ισοδύναμες με τη #P, την κλάση των AP-ισοδύναμων προβλημάτων με το #BIS, και με κάποια υποκλάση των προβλημάτων που επιδέχονται FPRAS αντίστοιχα. Ένας σπουδαίος στόχος για μια τέτοια μελέτη είναι η σύνδεση του αποδοτικού υπολογισμού, όσον αφορά τη μέτρηση λύσεων, με τις ήδη υπάρχουσες μετρητικές κλάσεις. Με τον όρο αποδοτική μέτρηση εννοούμε τη μέτρηση λύσεων σε πολυωνυμικό χρόνο ή με χρήση FPRAS. Επίσης διερευνώνται άλλες ενδιαφέρουσες ιδιότητες των υποκλάσεων της #P. Για παράδειγμα, εναλλακτικοί ορισμοί με βάση τη μέτρηση ορισμάτων σχέσεων, η υπολογιστική δυσκολία πλήρων προβλημάτων, τα οποία αποτυπώνουν τη δυσκολία της αντίστοιχης κλάσης. Στην ενότητα 3.5 ορίζουμε την κλάση TotL, και ερευνούμε κατά πόσο συμπεράσματα γνωστά για την TotP μπορούν να μεταφερθούν σε λογαριθμικού χώρου υπολογισμούς και να διατυπωθούν και γι&#x27;αυτή τη νέα κλάση.","abstract_has_math":false,"creators":["Χαλκή Αγγελική"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-11-19T05:26:35Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320955"],"render_values":[{"text":"uoadl:1320955","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320955","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320955","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1320955","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Χαλκή Αγγελική"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320955","https://pergamos.lib.uoa.gr/uoa/dl/object/1320955"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Στην παρούσα διπλωματική, μελετάμε μετρητικές κλάσεις οι οποίες περιέχονται στη #P. Μία προσέγγιση, η πιο διαδεδομένη στη Θεωρία Υπολογιστικής Πολυπλοκότητας, είναι ο ορισμός κλάσεων με βάση τη μηχανή Turing. Κλάσεις όπως οι #L, span-L και TotP, #PE προκύπτουν θέτοντας περιορισμούς στους υπολογιστικούς πόρους που διαθέτει μια μηχανή Turing. Μία δεύτερη προσέγγιση είναι αυτή της Περιγραφικής Πολυπλοκότητας. Μέσω αυτής τα μετρητικά προβλήματα εκφράζονται στη γλώσσα κάποιας λογικής, και μία κλάση πολυπλοκότητας ορίζεται με βάση τη λογική στην οποία εκφράζονται τα προβλήματά της. Κλάσεις όπως οι #FO, #RHΠ_1, #RHΣ_2 είναι ισοδύναμες με τη #P, την κλάση των AP-ισοδύναμων προβλημάτων με το #BIS, και με κάποια υποκλάση των προβλημάτων που επιδέχονται FPRAS αντίστοιχα. Ένας σπουδαίος στόχος για μια τέτοια μελέτη είναι η σύνδεση του αποδοτικού υπολογισμού, όσον αφορά τη μέτρηση λύσεων, με τις ήδη υπάρχουσες μετρητικές κλάσεις. Με τον όρο αποδοτική μέτρηση εννοούμε τη μέτρηση λύσεων σε πολυωνυμικό χρόνο ή με χρήση FPRAS. Επίσης διερευνώνται άλλες ενδιαφέρουσες ιδιότητες των υποκλάσεων της #P. Για παράδειγμα, εναλλακτικοί ορισμοί με βάση τη μέτρηση ορισμάτων σχέσεων, η υπολογιστική δυσκολία πλήρων προβλημάτων, τα οποία αποτυπώνουν τη δυσκολία της αντίστοιχης κλάσης. Στην ενότητα 3.5 ορίζουμε την κλάση TotL, και ερευνούμε κατά πόσο συμπεράσματα γνωστά για την TotP μπορούν να μεταφερθούν σε λογαριθμικού χώρου υπολογισμούς και να διατυπωθούν και γι'αυτή τη νέα κλάση.","In this thesis, we study counting classes that lie below #P. One approach, the most regular in Computational Complexity Theory, is the machine-based approach. Classes like #L, span-L and TotP, #PE are defined establishing space and time restrictions on Turing machine's computational resources. A second approach is Descriptive Complexity's approach. It characterizes complexity classes by the type of logic needed to express the languages in them. Classes deriving from this viewpoint, like #FO, #RHΠ_1, #RΣ_2, are equivalent to #P, the class of AP-interriducible problems to #BIS, and some subclass of the problems owning an FPRAS. A great objective of such an investigation is to gain an understanding of how “efficient counting” relates to these already defined classes. By “efficient counting” we mean counting solutions of a problem using a polynomial time algorithm or an FPRAS. Many other interesting properties of the classes considered and their problems have been examined. For example alternative definitions of counting classes using relation-based operators, and the computational difficulty of complete problems, since complete problems capture the difficulty of the corresponding class. Moreover, in Section 3.5 we define the log-space analog of the class TotP and explore how and to what extent results can be transferred from polynomial time to logarithmic space computation."]},{"key":"dc:title","label":"Title","values":["Counting below #P: Classes, problems and Descriptive Complexity"]}]}],"canonical_facts":{"dc:creator":["Χαλκή Αγγελική"],"dc:date":["2016"],"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 μπορούν να μεταφερθούν σε λογαριθμικού χώρου υπολογισμούς και να διατυπωθούν και γι'αυτή τη νέα κλάση.","In this thesis, we study counting classes that lie below #P. One approach, the most regular in Computational Complexity Theory, is the machine-based approach. Classes like #L, span-L and TotP, #PE are defined establishing space and time restrictions on Turing machine's computational resources. A second approach is Descriptive Complexity's approach. It characterizes complexity classes by the type of logic needed to express the languages in them. Classes deriving from this viewpoint, like #FO, #RHΠ_1, #RΣ_2, are equivalent to #P, the class of AP-interriducible problems to #BIS, and some subclass of the problems owning an FPRAS. A great objective of such an investigation is to gain an understanding of how “efficient counting” relates to these already defined classes. By “efficient counting” we mean counting solutions of a problem using a polynomial time algorithm or an FPRAS. Many other interesting properties of the classes considered and their problems have been examined. For example alternative definitions of counting classes using relation-based operators, and the computational difficulty of complete problems, since complete problems capture the difficulty of the corresponding class. Moreover, in Section 3.5 we define the log-space analog of the class TotP and explore how and to what extent results can be transferred from polynomial time to logarithmic space computation."],"dc:identifier":["uoadl:1320955","https://pergamos.lib.uoa.gr/uoa/dl/object/1320955"],"dc:language":["English"],"dc:title":["Counting below #P: Classes, problems and Descriptive Complexity"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:35Z"}