Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18412
Title: Εφαρμογές της Λογικής σε Αλγορίθμους Μέτρησης
Authors: Κανελλόπουλος, Σωτήριος
Παγουρτζής Αριστείδης
Keywords: Λογική
Περιγραφική Πολυπλοκότητα
Προσεγγιστικοί Αλγόριθμοι
Κλάσεις Πολυπλοκότητας
Προβλήματα Μέτρησης
Issue Date: 18-Jul-2022
Abstract: Σκοπός της παρούσας εργασίας είναι να μελετήσουμε χρήσιμες εφαρμογές της λογικής στη θεωρία αλγορίθμων και υπολογιστικής πολυπλοκότητας. Θα επικεντρωθούμε κυρίως στο πεδίο της περιγραφικής πολυπλοκότητας, ξεκινώντας από λογικές περιγραφές για κλάσεις προβλημάτων απόφασης (π.χ. τις P και NP) και στη συνέχεια επεκτείνοντας αυτές και για κλάσεις προβλημάτων μέτρησης. Όπως θα δούμε, οι λογικές περιγραφές αυτές χρησιμεύουν για την ταξινόμηση προβλημάτων σε κλάσεις, καθώς και τη μελέτη ιδιοτήτων των κλάσεων πολυπλοκότητας. Μάλιστα, σε ορισμένες περιπτώσεις μάς παρέχουν και εγγυήσεις για την ιεραρχία κάποιων κλάσεων. Παρουσιάζει ενδιαφέρον το γεγονός ότι με τη χρήση τέτοιων λογικών περιγραφών μπορεί ένα πρόβλημα να καταταγεί σε κλάσεις υπολογιστικής δυσκολίας μόνο από την εκφραστικότητα που χρειάζεται για να περιγραφεί η εκφώνησή του, χωρίς να μελετηθούν αλγόριθμοι για το αντίστοιχο πρόβλημα. Για μετρητικά προβλήματα, θα δούμε ότι η ύπαρξη αποδοτικών αλγορίθμων είναι σπάνια και για αυτό συνήθως στρεφόμαστε προς προσεγγιστικούς αλγορίθμους. Με βάση τις λογικές περιγραφές που έχουν δοθεί για την κλάση #P, μπορούν να δοθούν κάποιες εγγυήσεις για το ποια προβλήματα μέτρησης διαθέτουν προσεγγιστικό αλγόριθμο FPRAS. Κατ’ αναλογία με τις ήδη γνωστές λογικές περιγραφές που υπάρχουν για τις κλάσεις NP και #P, θα δώσουμε παρόμοιες περιγραφές για κάποιες λιγότερο μελετημένες κλάσεις που είναι συναφείς με μετρητικά προβλήματα. Αυτές οι περιγραφές μπορούν να φανούν χρήσιμες για την ιεράρχηση αυτών των κλάσεων, καθώς και για εναλλακτικές αποδείξεις ιδιοτήτων τους (π.χ. για το αν μια κλάση είναι κλειστή ως προς τομή).
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18412
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Διπλωματική_el17101.pdf841.34 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.