Αλγεβρική Μεθοδολογία Για Το Χαρακτηρισμό Της Πολυπλοκότητας Προβλημάτων Ικανοποίησης Περιορισμών

Abstract

Συνδυαστικά προβλήματα συναντάμε σε πολλούς τομείς της πληροφορικής. Γραφοθεωρητικά προβλήματα, προβλήματα ικανοποιησιμότητας, προβλήματα scheduling είναι απλώς μερικά παραδείγματα συνδυαστικών προβλημάτων. Όλα αυτά τα προβλήματα μπορούν να αντιμετωπιστούν ως υποκλάσεις ενός γενικευμένου συνδυαστικού προβλήματος του Constraint Satisfaction Problem. Έτσι ερευνώντας τις ιδιότητες του Constraint Satisfaction Problem κερδίζουμε γνώση για μια πολύ μεγάλη και χρήσιμη κλάση προβλημάτων.Εδώ θα ασχοληθούμε με την πολυπλοκότητα αυτών των προβλημάτων. Συγκεκριμένα η διπλωματική χωρίζεται σε 4 κεφάλαια. Στο πρώτο θα γνωρίσουμε το πρόβλημα, αλλά και θα δούμε εκφράσεις ήδη γνωστών προβλημάτων στη γλώσσα του CSP ώστε να πειστούμε για τη σημαντικότητά του. Στο δεύτερο κεφάλαιο θα ασχοληθούμε με την πολυπλοκότητα της κλάσης των προβλημάτων που μπορούμε να εκφράσουμε με CSP's. Θα δούμε ότι έχουμε ισχυρές ενδείξεις ότι υπάρχει ένα είδος διχοτόμησης της πολυπλοκότητας σε αυτά τα προβλήματα. Συγκεκριμένα ενώ υπάρχουν προβλήματα που είναι στο P αλλά και προβλήματα NP-complete μάλλον δεν υπάρχουν προβλήματα που είναι στο ενδιάμεσο. Στο τρίτο μέρος που είναι και το κύριο μέρος της διπλωματικής θα δούμε πως μπορούμε να χαρακτηρίσουμε υποκλάσεις CSPs που είναι tractable που λύνονται δηλαδή σε P. Θα φτάσουμε τελικά να βρούμε μια αντιστοίχηση μεταξύ σχέσεων και πράξεων και τελικά να χαρακτηρίζουμε Άλγεβρες που αντιστοιχούν σε κλάσεις προβλημάτων CSP ως προς την πολυπλοκότητά τους, μια ιδέα του 2005 που φαίνεται ότι θα ανοίξει νέους δρόμους στην έρευνα στον τομέα. Τέλος θα κλείσουμε με μια παρουσίαση της απόδειξης του Schaefer που πρακτικά άρχισε την έρευνα στο τομέα οπού χαρακτηρίζει όλα τα CSPs κάτω από τον περιορισμό ότι έχουμε σύμπαν δύο στοιχείων.