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