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