{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320942"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320942","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Complexity dichotomies of counting problems","abstract":"Στην παρούσα διπλωματική εργασία μελετάμε θεωρήματα διχοτομίας που αφορούν κυρίως προβλήματα μέτρησης. Ένα θεώρημα διχοτομίας για μια κλάση προβλημάτων, στην υπολογιστική πολυπλοκότητα, είναι μια πλήρης ταξινόμηση των προβλημάτων της οικογένειας σε υπολογιστικά εύκολα και σε υπολογιστικά δύσκολα προβλήματα, χωρίς ενδιάμεσα προβλήματα. Εξαιτίας του θεωρήματος του Ladner δε μπορούμε να βρούμε διχοτομία για ολόκληρες τις κλάσεις NP και #P, αλλά παρ' όλα αυτά υπάρχουν μεγάλες υποκλάσεις προβλημάτων που μοντελοποιούν πολλά \"φυσικά\" προβλήματα και για τις οποίες υπάρχουν θεωρήματα διχοτομίας. Ξεκινάμε με το μοντέλο των προβλημάτων ικανοποίησης περιορισμών ως πρόβλημα απόφασης (CSP) και στη συνέχεια μελετάμε τις κλάσεις των προβλημάτων μέτρησης ομομορφισμών γραφήματος, των προβλημάτων μέτρησης ικανοποίησης περιορισμών (#CSP) και των προβλημάτων Holant. Τέλος, θα κάνουμε μια σύντομη εισαγωγή στους ολογραφικούς αλγορίθμους, που είναι ειδικού τύπου πολυωνυμικοί αλγόριθμοι για προβλήματα μέτρησης.","abstract_html":"Στην παρούσα διπλωματική εργασία μελετάμε θεωρήματα διχοτομίας που αφορούν κυρίως προβλήματα μέτρησης. Ένα θεώρημα διχοτομίας για μια κλάση προβλημάτων, στην υπολογιστική πολυπλοκότητα, είναι μια πλήρης ταξινόμηση των προβλημάτων της οικογένειας σε υπολογιστικά εύκολα και σε υπολογιστικά δύσκολα προβλήματα, χωρίς ενδιάμεσα προβλήματα. Εξαιτίας του θεωρήματος του Ladner δε μπορούμε να βρούμε διχοτομία για ολόκληρες τις κλάσεις NP και #P, αλλά παρ&#x27; όλα αυτά υπάρχουν μεγάλες υποκλάσεις προβλημάτων που μοντελοποιούν πολλά &quot;φυσικά&quot; προβλήματα και για τις οποίες υπάρχουν θεωρήματα διχοτομίας. Ξεκινάμε με το μοντέλο των προβλημάτων ικανοποίησης περιορισμών ως πρόβλημα απόφασης (CSP) και στη συνέχεια μελετάμε τις κλάσεις των προβλημάτων μέτρησης ομομορφισμών γραφήματος, των προβλημάτων μέτρησης ικανοποίησης περιορισμών (#CSP) και των προβλημάτων Holant. Τέλος, θα κάνουμε μια σύντομη εισαγωγή στους ολογραφικούς αλγορίθμους, που είναι ειδικού τύπου πολυωνυμικοί αλγόριθμοι για προβλήματα μέτρησης.","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":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-11-19T05:26:35Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320942"],"render_values":[{"text":"uoadl:1320942","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320942","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320942","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%3A1320942","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":["2012"]},{"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":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320942","https://pergamos.lib.uoa.gr/uoa/dl/object/1320942"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Στην παρούσα διπλωματική εργασία μελετάμε θεωρήματα διχοτομίας που αφορούν κυρίως προβλήματα μέτρησης. Ένα θεώρημα διχοτομίας για μια κλάση προβλημάτων, στην υπολογιστική πολυπλοκότητα, είναι μια πλήρης ταξινόμηση των προβλημάτων της οικογένειας σε υπολογιστικά εύκολα και σε υπολογιστικά δύσκολα προβλήματα, χωρίς ενδιάμεσα προβλήματα. Εξαιτίας του θεωρήματος του Ladner δε μπορούμε να βρούμε διχοτομία για ολόκληρες τις κλάσεις NP και #P, αλλά παρ' όλα αυτά υπάρχουν μεγάλες υποκλάσεις προβλημάτων που μοντελοποιούν πολλά \"φυσικά\" προβλήματα και για τις οποίες υπάρχουν θεωρήματα διχοτομίας. Ξεκινάμε με το μοντέλο των προβλημάτων ικανοποίησης περιορισμών ως πρόβλημα απόφασης (CSP) και στη συνέχεια μελετάμε τις κλάσεις των προβλημάτων μέτρησης ομομορφισμών γραφήματος, των προβλημάτων μέτρησης ικανοποίησης περιορισμών (#CSP) και των προβλημάτων Holant. Τέλος, θα κάνουμε μια σύντομη εισαγωγή στους ολογραφικούς αλγορίθμους, που είναι ειδικού τύπου πολυωνυμικοί αλγόριθμοι για προβλήματα μέτρησης.","In this thesis we study dichotomy theorems mainly of counting problems. A dichotomy theorem for a class of problems, in computational complexity, is a complete classification of the problems of this class in computationally easy and computationally hard problems, without intermediate problems. Due to Ladner's theorem we cannot find a dichotomy for the whole classes NP and #P, however there are large subclasses of NP (#P), that model many \"natural\" problems, for which dichotomy theorems exist. We begin with the framework of the decision version of constraint satifaction problems (CSP) and then we study the classes of graph homomorphisms problems, of counting constraint satisfaction problems (#CSP) and of Holant problems. Finally, we will make a brief introduction to holographic algorithms, a special type of polynomial-time algorithms for counting problems."]},{"key":"dc:title","label":"Title","values":["Complexity dichotomies of counting problems"]}]}],"canonical_facts":{"dc:creator":["Δεσποτάκης Στυλιανός"],"dc:date":["2012"],"dc:description":["Στην παρούσα διπλωματική εργασία μελετάμε θεωρήματα διχοτομίας που αφορούν κυρίως προβλήματα μέτρησης. Ένα θεώρημα διχοτομίας για μια κλάση προβλημάτων, στην υπολογιστική πολυπλοκότητα, είναι μια πλήρης ταξινόμηση των προβλημάτων της οικογένειας σε υπολογιστικά εύκολα και σε υπολογιστικά δύσκολα προβλήματα, χωρίς ενδιάμεσα προβλήματα. Εξαιτίας του θεωρήματος του Ladner δε μπορούμε να βρούμε διχοτομία για ολόκληρες τις κλάσεις NP και #P, αλλά παρ' όλα αυτά υπάρχουν μεγάλες υποκλάσεις προβλημάτων που μοντελοποιούν πολλά \"φυσικά\" προβλήματα και για τις οποίες υπάρχουν θεωρήματα διχοτομίας. Ξεκινάμε με το μοντέλο των προβλημάτων ικανοποίησης περιορισμών ως πρόβλημα απόφασης (CSP) και στη συνέχεια μελετάμε τις κλάσεις των προβλημάτων μέτρησης ομομορφισμών γραφήματος, των προβλημάτων μέτρησης ικανοποίησης περιορισμών (#CSP) και των προβλημάτων Holant. Τέλος, θα κάνουμε μια σύντομη εισαγωγή στους ολογραφικούς αλγορίθμους, που είναι ειδικού τύπου πολυωνυμικοί αλγόριθμοι για προβλήματα μέτρησης.","In this thesis we study dichotomy theorems mainly of counting problems. A dichotomy theorem for a class of problems, in computational complexity, is a complete classification of the problems of this class in computationally easy and computationally hard problems, without intermediate problems. Due to Ladner's theorem we cannot find a dichotomy for the whole classes NP and #P, however there are large subclasses of NP (#P), that model many \"natural\" problems, for which dichotomy theorems exist. We begin with the framework of the decision version of constraint satifaction problems (CSP) and then we study the classes of graph homomorphisms problems, of counting constraint satisfaction problems (#CSP) and of Holant problems. Finally, we will make a brief introduction to holographic algorithms, a special type of polynomial-time algorithms for counting problems."],"dc:identifier":["uoadl:1320942","https://pergamos.lib.uoa.gr/uoa/dl/object/1320942"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Complexity dichotomies of counting problems"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:35Z"}