Back to search

National and Kapodistrian University of Athens

Complexity dichotomies of counting problems

Abstract

dc:description

Στην παρούσα διπλωματική εργασία μελετάμε θεωρήματα διχοτομίας που αφορούν κυρίως προβλήματα μέτρησης. Ένα θεώρημα διχοτομίας για μια κλάση προβλημάτων, στην υπολογιστική πολυπλοκότητα, είναι μια πλήρης ταξινόμηση των προβλημάτων της οικογένειας σε υπολογιστικά εύκολα και σε υπολογιστικά δύσκολα προβλήματα, χωρίς ενδιάμεσα προβλήματα. Εξαιτίας του θεωρήματος του Ladner δε μπορούμε να βρούμε διχοτομία για ολόκληρες τις κλάσεις NP και #P, αλλά παρ' όλα αυτά υπάρχουν μεγάλες υποκλάσεις προβλημάτων που μοντελοποιούν πολλά "φυσικά" προβλήματα και για τις οποίες υπάρχουν θεωρήματα διχοτομίας. Ξεκινάμε με το μοντέλο των προβλημάτων ικανοποίησης περιορισμών ως πρόβλημα απόφασης (CSP) και στη συνέχεια μελετάμε τις κλάσεις των προβλημάτων μέτρησης ομομορφισμών γραφήματος, των προβλημάτων μέτρησης ικανοποίησης περιορισμών (#CSP) και των προβλημάτων Holant. Τέλος, θα κάνουμε μια σύντομη εισαγωγή στους ολογραφικούς αλγορίθμους, που είναι ειδικού τύπου πολυωνυμικοί αλγόριθμοι για προβλήματα μέτρησης.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Δεσποτάκης Στυλιανός

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:1320942

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

Δεσποτάκης Στυλιανός. Complexity dichotomies of counting problems. 2012. https://pergamos.lib.uoa.gr/uoa/dl/object/1320942