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