National and Kapodistrian University of Athens
Complexity dichotomies for approximations of counting problems
Abstract
dc:descriptionΑυτή η διπλωματική αποτελεί μια επισκόπηση θεωρημάτων διχοτομίας για υπολογιστικά προβλήματα, και ειδικότερα προβλήματα μέτρησης. Θεώρημα διχοτομίας στην υπολογιστική πολυπλοκότητα είναι ένας πλήρης χαρασκτηρισμός των μελών μιας κλάσης προβλημάτων, σε υπολογιστικά δύσκολα και υπολογιστικά εύκολα, χωρίς να υπάρχουν προβλήματα ενδιάμεσης πολυπλοκότητας στην κλάση αυτή. Λόγω του θεωρήματος του Ladner, δεν μπορούμε να έχουμε διχοτομία για ολόκληρες τις κλάσεις NP και #P, παρόλα αυτά υπάρχουν μεγάλες υποκλάσεις της NP (#P) για τις οποίες ισχύουν θεωρήματα διχοτομίας. Συνεχίζουμε με την εκδοχή απόφασης του προβλήματος ικανοποίησης περιορισμών (CSP), μία κλάση προβλήμάτων της NP στην οποία δεν εφαρμόζεται το θεώρημα του Ladner. Δείχνουμε τα θεωρήματα διχοτομίας που υπάρχουν για ειδικές περιπτώσεις του CSP. Στη συνέχεια επικεντρωνόμαστε στα προβλήματα μέτρησης παρουσιάζοντας τα παρακάτω μοντέλα: Ομομορφισμοί γράφων, μετρητικό πρόβλημα ικανοποίησης περιορισμών (#CSP), και προβλήματα Holant. Αναφέρουμε τα θεωρήματα διχοτομίας που γνωρίζουμε γι' αυτά. Στο τελευταίο και κύριο κεφάλαιο, χαλαρώνουμε την απαίτηση ακριβών υπολογισμών, και αρκούμαστε στην προσέγγιση των προβλημάτων. Παρουσιάζουμε τα μέχρι σήμερα γνωστά θεωρήματα κατάταξης για το #CSP. Πολλά ερωτήματα στην περιοχή παραμένουν ανοιχτά. Το παράρτημα είναι μια εισαγωγή στους ολογραφικούς αλγορίθμους, μία πρόσφατη αλγοριθμική τεχνική για την εύρεση πολυωνυμικών αλγορίθμων (ακριβείς υπολογισμοί) σε προβλήματα μέτρησης.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Γκόμπελ-Μαγκάκης Ανδρέας-Νικόλαος
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1320940