Complexity dichotomies of counting problems

Διπλωματική Εργασία uoadl:1320942 204 Αναγνώσεις

Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2012-07-24
Έτος εκπόνησης:
2012
Συγγραφέας:
Δεσποτάκης Στυλιανός
Στοιχεία επιβλεπόντων καθηγητών:
Επίκ. Καθηγητής Αρ. Παγουρτζής, Καθηγητής Ε. Ζάχος, Λέκτορας Δ. Φωτάκης
Πρωτότυπος Τίτλος:
Complexity dichotomies of counting problems
Γλώσσες εργασίας:
Ελληνικά
Περίληψη:
Στην παρούσα διπλωματική εργασία μελετάμε θεωρήματα διχοτομίας που αφορούν
κυρίως προβλήματα μέτρησης. Ένα θεώρημα διχοτομίας για μια κλάση προβλημάτων,
στην υπολογιστική πολυπλοκότητα, είναι μια πλήρης ταξινόμηση των προβλημάτων
της οικογένειας σε υπολογιστικά εύκολα και σε υπολογιστικά δύσκολα προβλήματα,
χωρίς ενδιάμεσα προβλήματα. Εξαιτίας του θεωρήματος του Ladner δε μπορούμε να
βρούμε διχοτομία για ολόκληρες τις κλάσεις NP και #P, αλλά παρ' όλα αυτά
υπάρχουν μεγάλες υποκλάσεις προβλημάτων που μοντελοποιούν πολλά "φυσικά"
προβλήματα και για τις οποίες υπάρχουν θεωρήματα διχοτομίας. Ξεκινάμε με το
μοντέλο των προβλημάτων ικανοποίησης περιορισμών ως πρόβλημα απόφασης (CSP) και
στη συνέχεια μελετάμε τις κλάσεις των προβλημάτων μέτρησης ομομορφισμών
γραφήματος, των προβλημάτων μέτρησης ικανοποίησης περιορισμών (#CSP) και των
προβλημάτων Holant. Τέλος, θα κάνουμε μια σύντομη εισαγωγή στους ολογραφικούς
αλγορίθμους, που είναι ειδικού τύπου πολυωνυμικοί αλγόριθμοι για προβλήματα
μέτρησης.
Λέξεις-κλειδιά:
Διχοτομία, Πρόβλημα Ικανοποίησης Περιορισμών, Ομομορφισμοί Γραφήματος, Προβλήματα Holant, Ολογραφικοί Αλγόριθμοι
Ευρετήριο:
Όχι
Αρ. σελίδων ευρετηρίου:
0
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
40
Αριθμός σελίδων:
viii, 54