Στοιχεία επταμελούς επιτροπής:
Ελευθέριος Κυρούσης, Καθηγητής, Τμήμα Μαθηματικών ΕΚΠΑ (επιβλέπων)
Δημήτριος Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής ΕΚΠΑ (μέλος τριμελούς συμβουλευτικής επιτροπής)
Josep Díaz, Professor Emeritus, Department of Computer Science, Universitat Politècnica de Catalunya
Marcel Fernandez, Associate Professor, Telecommunications, Engineering School of Barcelona, Universitat Politècnica de Catalunya
Φωκίων Κολαΐτης, Distinguished Research Professor, Computer Science and Engineering Department, University of California, Santa Cruz
Δημήτριος Φωτάκης, Αναπληρωτής Καθηγητής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Περίληψη:
Σε αυτήν την διδακτορική διατριβή δουλεύουμε σε Προβλήματα Ικανοποίησης
Περιορισμών (Π.Ι.Π.), τα οποία αποτελούν μία από τις πιο καλά μελετημένες κα-
τηγορίες προβλημάτων στην Επιστήμη της Πληροφορικής. Στην συνήθη τους
μορφή, τα Π.Ι.Π. αποτελούνται από ένα σύνολο μεταβλητών που παίρνουν τιμές
από ένα κοινό πεδίο ορισμού. Οι μεταβλητές αυτές υπόκεινται σε διάφορους
περιορισμούς, που ορίζουν τους αποδεκτούς συνδυασμούς τιμών μίας λύσης.
Σε αυτό το πλαίσιο, υπάρχουν διάφορα ζητήματα που μπορούν να μας απασχο-
λήσουν: ο έλεγχος για το αν υπάρχει λύση, το να βρούμε ή να προσεγγίσουμε
μία λύση, ή το πόσο γρήγορα μπορεί να κάνει τα προηγούμενα μία αλγοριθμική
διαδικασία.
Πολλά ενδιαφέροντα προβλήματα στην περιοχή της Επιστήμης των Υπολογι-
στών μπορούν να αναπαρασταθούν ως Π.Ι.Π., όπως αυτό της ικανοποιησιμότη-
τας προτασιακών τύπων ή του χρωματισμού γραφημάτων. Ως αυτόνομο ερευ-
νητικό πεδίο, τα Π.Ι.Π. έχουν μελετηθεί εκτεταμένα, με αποτέλεσμα να υπάρχει
ένα μεγάλο πλήθος ερευνών που τα κατηγοριοποιούν με βάση την υπολογιστι-
κή πολυπλοκότητά τους και που διαχωρίζουν τα (πολυωνυμικώς) επιλύσιμα από
τα NP-δύσκολα. Πέραν τούτου, έχουν αναπτυχθεί πολλά εργαλεία γι αυτά τα
προβλήματα, όπως πολυωνυμικού χρόνου αλγόριθμοι για συγκεκριμένες κατη-
γορίες Π.Ι.Π., πιθανοτικοί αλγόριθμοι που βρίσκουν ή προσεγγίζουν λύσεις σε
Π.Ι.Π. που ικανοποιούν ορισμένες συνθήκες και αλγεβρικές προσεγγίσεις μέσω
των οποίων συσχετίζουμε την υπολογιστική τους πολυπλοκότητα με την δομή
του συνόλου των περιορισμών τους.
Στην παρούσα εργασία, ξεκινάμε με την παρουσίαση διαφόρων προσεγγίσε-
ων στα Π.Ι.Π.: μέσω Προτασιακής, Πρωτοβάθμιας ή Δευτεροβάθμιας Λογικής
και μέσω ομομορφισμών. Μελετούμε επίσης την παραλλαγή των Πολυ-ειδών
Π.Ι.Π., των οποίων οι μεταβλητές χωρίζονται σε διαφορετικά είδη και παίρνουν
τιμές από διακριτά και ανεξάρτητα πεδία ορισμών. Κάποιες από αυτές τις παραλ-
λαγές και προσεγγίσεις δίνονται ώστε να φανεί η ευρύτητα του πλαισίου μέσα
910
στο οποίο δουλεύουμε, ενώ άλλες χρησιμοποιούνται στα ίδια τα αποτελέσματά
μας.
Το πρώτο μέρος των αποτελεσμάτων μας αφορά την λεγόμενη πιθανοτι-
κή προσέγγιση. Σχεδιάζουμε αλγορίθμους που (ι) αποδεικνύουν συνθήκες οι
οποίες εγγυώνται την ύπαρξη λύσης σε στιγμιότυπα ενός Π.Ι.Π. και (ιι) σε
περίπτωση που υπάρχει λύση, την βρίσκουν σε πολυωνυμικό χρόνο. Οι λίσεις
αυτές συνήθως αναπαριστόνται από σημεία ενός πιθανοτικού χώρου στα οποία
δεν ισχύει κανένα από μία σειρά γεγονότα τα οποία κρίνονται ως ‘ανεπιθύμητα’.
Δουλεύουμε με το Τοπικό Λήμμα του Lovász (Lovász Local Lemma) και την
παραλλαγή του, το Λήμμα τουShearer . Αυτά τα λήμματα, δοθέντων κάποιων
άνω φραγμάτων στην πιθανότητα μη-επιθυμητών γεγονότων να συμβούν, κα-
θώς και στο πλήθος των μεταξύ τους συσχετισμών και εξαρτήσεων, μας δίνουν
συνθήκες κάτω από τις οποίες υπάρχει λύση. Ακολουθώντας τους Moser και
Tardos, υποθέτουμε ότι όλα τα γεγονότα ορίζονται μέσω ανεξάρτητων τυχαίων
μεταβλητών. Παρόλο που αυτό είναι ένα πιο περιορισμένο πεδίο σε σχέση με
το να δουλεύαμε με γενικούς πιθανοτικούς χώρους, είναι ένα ευρύ πλαίσιο που
ταιριάζει με αυτό των Π.Ι.Π. και στο οποίο μπορούμε εύκολα να σχεδιάσουμε
αλγορίθμους.
Συγκεκριμένα, εισάγουμε δύο νέες έννοιες εξάρτησης μεταξύ των γεγο-
νότων, την κατευθυνόμενη ασύμμετρη εξάρτηση μεταβλητής (variable - di-
rected lopsidependency - VDL) και την κατευθυνόμενη εξάρτηση. Και οι δύο
αυτές έννοιες είναι σχεδιασμένες ώστε να επιτρέπουν την αλγοριθμική επεξερ-
γασία αρνητικά συσχετισμένων γεγονότων. Είναι σύνηθες οι εξαρτήσεις με-
ταξύ των γεγονότων να αποτυπώνονται στα λεγόμενα γραφήματα εξάρτησης,
των οποίων οι κορυφές αντιστοιχούν στα γεγονότα και τα γεγονότα που δεν
ενώνονται με ακμές θεωρούνται ανεξάρτητα. Ως εκ τούτου, συγκρίνουμε τα
κατευθυνόμενα γραφήματα εξάρτησης που προκύπτουν από τις δύο παραπάνω
έννοιες που εισαγάγαμε, με άλλα τέτοιου είδους γραφήματα που χρησιμοποιο-
ύνται στην βιβλιογραφία. Ειδικότερα, δείχνουμε ότι το γράφημα της κατευθυ-
νόμενης εξάρτησης είναι πιο αραιό από τα περισσότερα τέτοια γραφήματα, κάτι
που επιτρέπει να αποδειχθούν πιο ισχυρές μορφές του Τοπικού Λήμματος.
Στην συνέχεια, αποδεικνύουμε την απλή μορφή του λήμματος αυτού για την
VDL. Συγκεκριμένα, σχεδιάζουμε έναν αλγόριθμο ο οποίος, δεδομένου ότι η
πιθανότητα των γεγονότων φράσσεται από έναν αριθμό p ∈ [0, 1), ότι το VDL
γράφημα έχει μέγιστο βαθμό d και ότι epd ≤ 1, βρίσκει σε πολυωνυμικό χρόνο
ένα σημείο στον πιθανοτικό χώρο τέτοιο ώστε κανένα από τα μη επιθυμητά
γεγονότα να μην ισχύει. Αυτό φυσικά συνεπάγεται και την ύπαρξη τέτοιου
σημείου. Στην συνέχεια, αποδεικνύουμε την μη-συμμετρική εκδοχή του λήμ-11
ματος για το γράφημα κατευθυνόμενης εξάρτησης. Σε αυτήν την εκδοχή, η
πιθανότητα κάθε γεγονότος φράσσεται από έναν αριθμό που σχετίζεται με την
πιθανότητα όλων των εξαρτωμένων από αυτό γεγονότων. Τέλος, αποδεικνύου-
με και το πιο ισχυρό Λήμμα του Shearer για το μη-κατευθυνόμενο γράφημα
που προκύπτει αν αγνοήσουμε τις κατευθύνσεις στο γράφημα κατευθυνόμενης
εξάρτησης. Σε αυτό το λήμμα, οι πιθανότητες των γεγονότων φράσσονται από
πολυώνυμα επί των ανεξάρτητων συνόλων του γραφήματος.
Οι αποδείξεις αυτών των εκδοχών των λημμάτων αυτών γίνονται μέσω μίας
απευθείας πιθανοτικής ανάλυσης του πλήθους των βημάτων που κάνουν οι αλ-
γόριθμοι μας. Για να το επιτύχουμε αυτό, φράσσουμε την πιθανότητα να ε-
κτελέσουν τουλάχιστον n βήματα από μια σχέση αναδρομής, την οποία στην
συνέχεια επιλύουμε με αναλυτικά εργαλεία, όπως την εκδοχή της Φόρμουλας Α-
ντιστροφής του Lagrange που έχουν αποδείξει οι Bender και Richmond, ή την
Φόρμουλα του Gelfand για την φασματική νόρμα πινάκων. Αντίθετα, οι μέχρι
τώρα αλγοριθμικές προσεγγίσεις υπολογίζουν την αναμενόμενη τιμή των βη-
μάτων των αλγορίθμων. Θεωρούμε πως αυτό το γεγονός από μόνο του κάνει
την παραπάνω προσέγγισή ενδιαφέρουσα. Παρόλα αυτά, εφαρμόσαμε τις με-
θόδους μας σε δύο ενδιαφέροντα υπολογιστικά προβλήματα. Αρχικά, δείχνου-
με ότι 2∆ − 1 χρώματα αρκούν για να βάψουμε τις ακμές ενός γραφήματος
με τέτοιων τρόπο ώστε, πρώτον, να μην υπάρχουν προσπίπτουσες ακμές ίδιου
χρώματος και, δεύτερον, να μην υπάρχουν διχρωματικοί κύκλοι. Το αποτέλεσμα
αυτό είναι βέλτιστο για αλγορίθμους τύπου Moser, όπως παρατήρησαν οι Cai et
al. [Acyclic edge colourings of graphs with large girth. Random Structures &
Algorithms, 50(4):511–533, 2017]. Ακόμη, δείχνουμε πως να κατασκευάσου-
με c-διαχωριστικούς κώδικες των οποίων η πληροφορία σε κάθε ψηφίο είναι η
βέλτιστη που χει βρεθεί στην βιβλιογραφία. Οι c-διαχωριστικοί κώδικες είναι
πίνακες διάστασης M ×n, με στοιχεία από ένα αλφάβητο Q, ώστε, για κάθε δύο
υποσύνολα U , V το πολύ c γραμμών τους, να υπάρχει τουλάχιστον μία στήλη
της οποίας τα σύνολα των στοιχείων στο U και αυτά του V να είναι ξένα. Πα-
ρ ́ότι αυτοί οι κώδικες είναι πολύ χρήσιμοι στις εφαρμογές, οι κατασκευές τους
είναι πολύ σπάνιες.
Το δεύτερο μέρος της δουλειάς μας είναι στην Θεωρία Κοινωνικών Προτι-
μήσεων και, πιο συγκεκριμένα, στον Συμψηφισμό Κρίσεων, όπου ένα σύνολο
ατόμων θέλει να αποφασίσει συλλογικά ένα σύνολο ζητημάτων, και που οι δυ-
νατοί συνδυασμοί ψήφων, τόσο για το κάθε άτομο ξεχωριστά, όσο και για την
συλλογική απόφαση υπακούν σε κάποιους περιορισμούς, οι οποίοι επιβάλουν
κάποια έννοια λογικής συνέπειας. Στόχος είναι να βρεθούν κανόνες συμψη-
φισμού που διατηρούν αυτούς τους περιορισμούς και που δεν εκφυλίζονται σε12
δικτατορίες, δηλαδή σε κανόνες που καταλήγουν πάντα στις επιλογές ενός συ-
γκεκριμένου ατόμου.
Αρχικά, εξετάζουμε την περίπτωση που οι περιορισμοί αυτοί μας δίνονται ως
ένα σύνολο X m-αδικών διανυσμάτων με στοιχεία από ένα πεδίο ορισμού D,
όπου m είναι το πλήθος των ζητημάτων επί των οποίων ψηφίζουν τα άτομα.
Το X λοιπόν περιέχει τους επιτρεπόμενους συνδυασμούς ψήφων επί των θε-
μάτων και κάθε διάνυσμα εκτός του X θεωρείται μη λογικά συνεπές. Σε αυτό
το πλαίσιο, χαρακτηρίζουμε τα πεδία δυνατότητας, τα σύνολα X δηλαδή όπου
μπορούμε να βρούμε μη-δικτατορικούς συμψηφιστές, μέσω των ειδών των συμ-
ψηφιστών που δέχονται. Στην συνέχεια, χαρακτηρίζουμε με αντίστοιχο τρόπο
τα ομοιόμορφα πεδία δυνατότητας, τα οποία δέχονται συμψηφιστές οι οποίοι δεν
είναι δικτατορικοί ακόμη κι όταν περιορίζονται σε οποιοδήποτε θέμα και δυαδι-
κό υποσύνολο δυνατών θέσεων ως προς το θέμα αυτό. Δείχνουμε επίσης ότι
τα πολυειδή Π.Ι.Π. που ορίζονται πάνω σε ομοιόμορφα πεδία δυνατότητας είναι
πολυωνυμικώς επιλύσιμα, ενώ τα Π.Ι.Π. που ορίζονται σε σύνολα που δεν ε-
ίναι τέτοια, είναι NP-δύσκολα, συνδέοντας έτσι την δυνατότητα μη δικτατορικού
συμψηφισμού με μια διχοτομία στην πολυπλοκότητα των πολυειδών Π.Ι.Π.
Στην συνέχεια, ασχολούμαστε με την περίπτωση που το X ορίζεται πάνω
σε δυαδικό πεδίο ορισμού και μας δίνεται ως το σύνολο αληθοτιμών μιας προτα-
σιακής φόρμουλας. Στην βιβλιογραφία, τέτοιες φόρμουλες ονομάζονται περιο-
ρισμοί ακεραιότητας. Αποδεικνύουμε συντακτικούς χαρακτηρισμούς για φόρ-
μουλες που μας δίνουν (ομοιόμορφα) πεδία δυνατότητας, καθώς και πεδίων που
δέχονται ένα πλήθος από μη-δικτατορικούς συμψηφιστές με ενδιαφέρουσες ι-
διότητες, που έχουν εμφανιστεί στην βιβλιογραφία. Δείχνουμε επίσης πως να
αναγνωρίζουμε αποδοτικά τέτοιους συντακτικούς τύπους αλλά και πως να τους
κατασκευάζουμε μέσω ενός πεδίου με τις κατάλληλες ιδιότητες.
Τέλος, ασχολούμαστε με το πρόβλημα της αναγνώρισης ενός πεδίου που
δέχεται (ομοιόμορφους) μη δικτατορικούς συμψηφιστές. Στην περίπτωση που
το X μας έχει δοθεί ως σύνολο διανυσμάτων, σχεδιάζουμε πολυωνυμικούς αλ-
γορίθμους που το επιλύουν. Αν το X δίνεται είτε ως το σύνολο αληθείας μιας
προτασιακής φόρμουλας, είτε ως ένα σύνολο λογικά συνεπών κρίσεων ενός συ-
νόλου τέτοιων τύπων, δηλαδή μιας αντζέντας, όπως ήταν κι ο αρχικός τρόπος
μελέτης της συγκεκριμένης περιοχής, δίνουμε άνω και κάτω φράγματα στην υ-
πολογιστική πολυπλοκότητα αυτών των προβλημάτων, μέσω της πολυωνυμικής
ιεραρχίας. Αντίστοιχα αποτελέσματα βρίσκουμε και στις περιπτώσεις που ελέγ-
χουμε για μη δικτατορικούς συμψηφιστές με επιθυμητές ιδιότητες που έχουν
μελετηθεί στην βιβλιογραφία.
