Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Γκόμπελ-Μαγκάκης Ανδρέας-Νικόλαος. Complexity dichotomies for approximations of counting problems. 2012. https://pergamos.lib.uoa.gr/uoa/dl/object/1320940