Εφαρμογές της Λογικής σε Αλγορίθμους Μέτρησης

Abstract

Σκοπός της παρούσας εργασίας είναι να μελετήσουμε χρήσιμες εφαρμογές της λογικής στη θεωρία αλγορίθμων και υπολογιστικής πολυπλοκότητας. Θα επικεντρωθούμε κυρίως στο πεδίο της περιγραφικής πολυπλοκότητας, ξεκινώντας από λογικές περιγραφές για κλάσεις προβλημάτων απόφασης (π.χ. τις P και NP) και στη συνέχεια επεκτείνοντας αυτές και για κλάσεις προβλημάτων μέτρησης. Όπως θα δούμε, οι λογικές περιγραφές αυτές χρησιμεύουν για την ταξινόμηση προβλημάτων σε κλάσεις, καθώς και τη μελέτη ιδιοτήτων των κλάσεων πολυπλοκότητας. Μάλιστα, σε ορισμένες περιπτώσεις μάς παρέχουν και εγγυήσεις για την ιεραρχία κάποιων κλάσεων. Παρουσιάζει ενδιαφέρον το γεγονός ότι με τη χρήση τέτοιων λογικών περιγραφών μπορεί ένα πρόβλημα να καταταγεί σε κλάσεις υπολογιστικής δυσκολίας μόνο από την εκφραστικότητα που χρειάζεται για να περιγραφεί η εκφώνησή του, χωρίς να μελετηθούν αλγόριθμοι για το αντίστοιχο πρόβλημα. Για μετρητικά προβλήματα, θα δούμε ότι η ύπαρξη αποδοτικών αλγορίθμων είναι σπάνια και για αυτό συνήθως στρεφόμαστε προς προσεγγιστικούς αλγορίθμους. Με βάση τις λογικές περιγραφές που έχουν δοθεί για την κλάση #P, μπορούν να δοθούν κάποιες εγγυήσεις για το ποια προβλήματα μέτρησης διαθέτουν προσεγγιστικό αλγόριθμο FPRAS. Κατ’ αναλογία με τις ήδη γνωστές λογικές περιγραφές που υπάρχουν για τις κλάσεις NP και #P, θα δώσουμε παρόμοιες περιγραφές για κάποιες λιγότερο μελετημένες κλάσεις που είναι συναφείς με μετρητικά προβλήματα. Αυτές οι περιγραφές μπορούν να φανούν χρήσιμες για την ιεράρχηση αυτών των κλάσεων, καθώς και για εναλλακτικές αποδείξεις ιδιοτήτων τους (π.χ. για το αν μια κλάση είναι κλειστή ως προς τομή).