Ιδιότητες συναρτήσεων μέτρησης πλήθους λύσεων σε προβλήματα με εύκολη απόφαση ύπαρξης λύσης: πληρότητα, προσεγγισιμότητα, μαρκοβιανές αλυσίδες, αλλαγές φάσης

Abstract

Η κλάση πολυπλοκότητας #P είναι η κλάση συναρτήσεων που μετρούν τον αριθμό των λύσεων σε προβλήματα απόφασης στο NP, π.χ. η #SAT είναι η συνάρτηση που με είσοδο έναν λογικό τύπο ϕ επιστρέφει τον αριθμό ικανοποιητικών αναθέσεων του ϕ: Το πλήθος των λύσεων για NP-πλήρη προβλήματα είναι δύσκολο να μετρηθεί, αλλά υπάρχουν δύσκολα προβλήματα καταμέτρησης με τo αντίστοιχο πρόβλημα απόφασης στο P. Η TotP είναι μια υποκλάση της #P που περιέχει όλα τα αυτοαναγώγιμα προβλήματα μέτρησης με εύκολη απόφαση ύπαρξης λύσης. Περιέχει πολλά ενδιαφέροντα προβλήματα από πολλές επιστημονικές περιοχές. Οι Cook αναγωγές θολώνουν τις δομικές διαφορές μεταξύ των προβλημάτων καταμέτρησης, π.χ. το PERMANENT είναι #P-πλήρες, αλλά ανήκει επίσης στην TotP, επομένως απαιτούνται αυστηρότερες αναγωγές προκειμένου να χαρακτηριστεί πλήρως η πολυπλοκότητα ενός προβλήματος μέτρησης: οι λεγόμενες parsimonious (φειδωλές) αναγωγές, οι οποίες είναι εκείνες που διατηρούν ακριβώς τις τιμές των συναρτήσεων. Η ύπαρξη TotP-πλήρων προβλημάτων κάτω από φειδωλές αναγωγές ήταν ένα ανοιχτό πρόβλημα εδώ και δέκα περίπου χρόνια. Ο πρώτος σκοπός αυτής της εργασίας είναι να παρουσιάσει τα πρώτα τέτοια προβλήματα (κεφάλαιο 2). Αυτά τα προβλήματα σχετίζονται με την ικανοποίηση Boolean κυκλωμάτων (και συγκεκριμένα το #tree-monotone-circuit-SAT) και τύπων (συγκεκριμένα το #clustered-monotone-SAT ή #CM-SAT), και με το πρόβλημα της εκτίμησης του μεγέθους ενός backtracking δέντρου (συγκεκριμένα το Size-of-Subtree). Ένα σημαντικό θεώρημα που αποδεικνύουμε είναι ότι το #SAT ανάγεται στο #CM-SAT υπό αναγωγές που διατηρούν την προσεγγισιμότητα. Η δειγματοληψία και η κατά προσέγγιση μέτρηση πραγματοποιούνται συνήθως με τη χρήση μαρκοβιανών αλυσίδων. Ωστόσο, για το #SAT είναι γνωστό ότι δεν μπορούμε να σχεδιάσουμε μη αναγώγιμες μαρκοβιανές αλυσίδες, των οποίων ο χώρος καταστάσεων να είναι το σύνολο ικανοποιητικών αναθέσεων ενός τύπου που δίνεται ως είσοδος, εξαιτίας ενός φαινομένου διασκορπισμού του συνόλου των λύσεων. Αντίθετα, το σύνολο των λύσεων του #CM-SAT, καθώς και του Size-of-Subtree, συνδέεται με έναν συγκεκριμένο τρόπο που επιτρέπει το σχεδιασμό μη αναγώγιμων μαρκοβιανών αλυσίδων. Στο κεφάλαιο 4 σχεδιάζουμε και μελετάμε μερικές μαρκοβιανές αλυσίδες, των οποίων ο χώρος καταστάσεων είναι το σύνολο των λύσεων των παραπάνω προβλημάτων. Αναλύουμε το χρόνο σύγκλισης, τις στάσιμες κατανομές τους και την πολυπλοκότητα του υπολογισμού των συντελεστών κανονικοποίησης, όπως και του μεγέθους του συνόλου υποστήριξης των στάσιμων κατανομών. Τα κύρια αποτελέσματα της μελέτης μας είναι καταρχάς ότι το #SAT ανάγεται στον υπολογισμό του συντελεστή κανονικοποίησης της στάσιμης κατανομής για μια οικογένεια μαρκοβιανών αλυσίδων που σχεδιάζουμε. Με άλλα λόγια, ο υπολογισμός αυτού του συντελεστή κανονικοποίησης είναι #P-πλήρης. Δεύτερον, αυτός ο συντελεστής κανονικοποίησης μπορεί να προσεγγιστεί με FPRAS (δηλ. με ένα αυθαίρετα μικρό πολλαπλασιαστικό σφάλμα σε πολυωνυμικό χρόνο). Παραμένει ανοικτό το ερώτημα εάν αυτός ο συντελεστής κανονικοποίησης μπορεί να υπολογιστεί είτε με ακρίβεια είτε με ένα μικρό απόλυτο σφάλμα. Ωστόσο, δείχνουμε ότι το τελευταίο είναι αδύνατο εκτός αν NP = RP. Παρατηρούμε τότε ένα ενδιαφέρον φαινόμενο. Για κάθε είσοδο σε ένα πρόβλημα στην TotP θεωρήσαμε δύο διαφορετικές μαρκοβιανές αλυσίδες που συγκλίνουν σε δύο διαφορετικές κατανομές P1, P2, με συντελεστές κανονικοποίησης Z1, Z2 αντίστοιχα. Στο κεφάλαιο 5 δείχνουμε ότι μπορούμε να γενικεύσουμε τις δύο παραπάνω κατανομές πιθανότητας με ένα ενιαίο μοντέλο P(λ), λ >0 , έτσι ώστε P(1) = P1 και P(2) = P2: Αυτό το μοντέλο παρουσιάζει εντελώς διαφορετική συμπεριφορά για λ = 1 και λ = 2: Και για τα δύο λ = 1 και λ = 2, ο υπολογισμός του Zλ είναι δύσκολος (#P-πλήρης), αλλά για λ = 1 έχουμε • εκθετικό χρόνο σύγκλισης της αντίστοιχης αλυσίδας Markov • αδυναμία ύπαρξης FPRAS για το Z1 εκτός NP = RP. και για λ = 2 έχουμε • πολυωνυμικό χρόνο σύγκλισης της αντίστοιχης αλυσίδας Markov • FPRAS για το Z2. Το ερώτημα που τίθεται είναι τι ισχύει για τις υπόλοιπες τιμές του λ > 0. Σχεδιάζουμε (στο κεφάλαιο 5) μια μαρκοβιανή αλυσίδα, παραμετροποιημένη από το λ, που γενικεύει τις δύο διαφορετικές μαρκοβιανές αλυσίδες που μελετήθηκαν στο κεφάλαιο 4. Αυτή η μαρκοβιανή αλυσίδα Mλ ακολουθεί τον κανόνα του Metropolis και συγκλίνει σε μια κατανομή Pλ την οποία προσδιορίζουμε. Δείχνουμε ότι υπάρχει αλλαγή φάσης ως προς τον χρόνο σύγκλισης της Mλ συναρτήσει του λ. Συγκεκριμένα, υπάρχει μια ασυνεχής μετάβαση από εκθετικό σε πολυωνυμικό χρόνο σύγκλισης για λ στο διάστημα [1,2] που εξαρτάται από το δέντρο. Για το πλήρες δέντρο, όπως και για τα δέντρα που αποτελούν δύσκολα στιγμιότυπα του προβλήματος Size-of-Subtree, η αλλαγή φάσης είναι στο λ = 2, ενώ για το μονοπάτι (το οποίο βρίκεται στον αντίποδα του πλήρους δέντρου) η αλλαγή φάσης είναι στο λ = 1. Επίσης αποδεικνύουμε ότι υπάρχει αλλαγή φάσης στην πολυπλοκότητα του προβλήματος από δύσκολα προσεγγίσιμο (ΝP-hard to approximate) σε προσεγγίσιμο με FPRAS για κάποιο λ στο διάστημα [1, 2]. Μια παράλληλη κατεύθυνση αυτής της διατριβής αφορά την προσέγγιση των συναρτήσεων στην TotP. Είναι γνωστό ότι FPRAS για όλα τα προβλήματα στην TotP είναι εφικτό αν και μόνο αν NP = RP. Το ίδιο ισχύει και για τη #P. Ωστόσο, στο κεφάλαιο 3 δείχνουμε ότι μπορούμε να έχουμε κάποια καλύτερα αποτελέσματα για την TotP σε σχέση με την #P. Πρώτον, για κάθε πρόβλημα στην TotP, αν ο αριθμός λύσεων είναι x, μπορούμε να υπολογίσουμε ακριβώς αυτόν τον αριθμό σε χρόνο x•poly(n); όπου n είναι το μέγεθος της εισόδου. Με άλλα λόγια, αν ο αριθμός των λύσεων είναι πολυωνυμικός (δηλαδή μικρός), μπορούμε να τις μετρήσουμε ακριβώς σε πολυωνυμικό χρόνο. Δεύτερον, αν ο αριθμός των λύσεων είναι 2^n/x, μπορούμε να έχουμε RAS (δηλαδή αυθαίρετα μικρό πολλαπλασιαστικό σφάλμα) σε χρόνο poly(n, x): Με άλλα λόγια, εάν ο αριθμός των λύσεων είναι 2^n/poly(n) (δηλαδή μεγάλος), μπορούμε να έχουμε FPRAS. Τρίτον, αν συνδυάσουμε τα παραπάνω αποτελέσματα με το γνωστό γεγονός ότι όλα τα προβλήματα στην #Ρ επιδέχονται μια προσθετικού σφάλματος προσέγγιση, παίρνουμε καλύτερα εκθετικού χρόνου αλγοριθμικά αποτελέσματα για την TotP από τα αντίστοιχα γνωστά αποτελέσματα για την #Ρ. Παραμένει ανοιχτό το ερώτημα εάν αυτά τα αποτελέσματα είναι βέλτιστα υπό μια fine-grained οπτική πολυπλοκότητας (δηλ. υπό κάποια παραδοχή ανάλογη με την SETH, η οποία δηλώνει χοντρικά ότι το SAT χρειάζεται για να λυθεί χρόνο Θ(2^n)). Επίσης αφού παρατηρούμε ότι το TotP-πλήρες πρόβλημα Size-of-Subtree είναι εύκολο να προσεγγιστεί σε πολλές περιπτώσεις, προσδιορίζουμε μια οικογένεια για την οποία αποδεικνύουμε ότι περιέχει δύσκολα στιγμιότυπα του προβλήματος. Το τελευταίο θέμα που εξετάζει αυτή η διατριβή (στο κεφάλαιο 3) αφορά μια διαισθητική πεποίθηση πολλών επιστημόνων ότι τα μόνα προβλήματα στη #Ρ που μπορεί να έχουν FPRAS ανήκουν στην TotP, και δεν υπάρχουν γνωστά αντιπαραδείγματα σε αυτή την εικασία. Αποδεικνύουμε ότι αυτή η εικασία είναι λάθος εκτός εάν P = RP. Προκειμένου να το δείξουμε αυτό, εισάγουμε δύο νέες κλάσεις πολυπλοκότητας #RP1 και #RP2. Δείχνουμε επίσης ότι η κλάση των προβλημάτων που επιδέχονται FPRAS βρίσκεται μεταξύ αυτών των δύο κλάσεων και ότι αυτές οι κλάσεις δεν συμπίπτουν εκτός αν NP = RP. Τέλος, για να αποκτήσουμε μια πιο ξεκάθαρη εικόνα των σχέσεων των παραπάνω κλάσεων με την #P και την TotP (και μερικές άλλες σχετικές κλάσεις), μελετάμε τους εγκλεισμούς μεταξύ τους και παρουσιάζουμε τους τέσσερις δυνατούς κόσμους σε σχέση με το NP v.s. RP και το RP v.s. P πρόβλημα.