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

Abstract

The complexity class #P is the class of functions that count the number of solutions to problems in NP, e.g. #SAT is the function that on input a formula ϕ returns the number of satisfying assignments of ϕ. NP-complete problems are hard to count, but there exist hard counting problems with decision version in P. TotP is a subclass of #P that contains all self-reducible problems with easy decision version. It contains many interesting problems from many scientific areas.Cook reductions blur structural differences between counting problems, e.g. the PERMANENT is #P complete, but it also belongs to TotP, thus more strict reductions are needed in order to fully characterize the complexity of a counting problem; the so called parsimonious reductions, which are those that preserve exactly the values of the functions. The existence of TotP-complete problems under parsimonious reductions (besides the generic one), was an open question. The first purpose of this thesis is to present the first such problems (chapter 2). These problems are related to satisfiability of Boolean circuits (namely #tree-monotone-circuit-SAT) and formulas (namely the clustered monotone SAT, or #CM-SAT ), and to the problem of estimating the size of a backtracking tree (namely the Size-of-Subtree problem).An important theorem that we prove is that #SAT reduces to #CMSAT under approximation preserving reductions. Sampling and approximate counting are usually performed with the use of Markov chains. However for #SAT it is known that we cannot design irreducible Markov chains whose state space is the set of satisfying assignments of an input formula, due to scattering phenomenon of the set of solutions. On the contrary, the set of solutions of #CM-SAT, as well as of Size-of-Subtree, is connected in a particular way that permits the design of irreducible Markov chains.In chapter 4 we design and study some Markov chains whose state space is the set of solutions of the above problems. We analyse their mixing time, their stationary distributions, and the complexity of computing the normalizing factors and the size of the support of the stationary distributions. The main results of our study is firstly that #SAT is reduced to the computation of the normalizing factor of the stationary distribution of a family of Markov chains that we design. In other words, the computation of this normalizing factor is #P-complete. Secondly this normalizing factor can be approximated with FPRAS, (i.e. with an arbitrarily small multiplicative error in polynomial time). It remains an open question whether this normalizing factor can be computed either exactly or with a small absolute error. However we show that the latter is impossible unless NP=RP.We then observe an interesting phenomenon. For every input to a problem in TotP we considered two different Markov chains that converge to two different stationary distributions P1, P2, with normalizing factors Z1, Z2 respectively. In chapter 5 we show that we can generalize the above two probability distributions by a single model P(λ), λ>0, so that P(1) = P1and P(2) = P2: This model exhibits a completely different behaviour for λ = 1 and λ = 2: For both λ = 1 and λ = 2, the computation of Zλ is hard (#P-complete), but for λ = 1 we have• exponential mixing time of the respective Markov chain• impossibility of FPRAS for Z1 unless NP=RP.and for λ = 2 we have• polynomial mixing time of the respective Markov chain• FPRAS for Z2.The question that arises is what happens for the other values of λ > 0. We design (in chapter 5) a Markov chain, parametrized by λ, that generalizes the two different Markov chains studied in chapter 4. This Markov chain Mλ follows the Metropolis rule, and converges to P(λ). We show that a phase transition occurs to the running time of Mλ with respect to λ. In particular there is a discontinuous transition from polynomial to exponential mixing time for λ in [1,2] that depends on the input tree. The complexity of computing Zλ also exhibits a phase transition from NP-hard to approximate to approximable with FPRAS for λ in [1,2].A parallel direction of this thesis concerns the approximability of functions in TotP. It is known that FPRAS for all problems in TotP is possible if and only if NP=RP. The same holds for #P. However in chapter 3 we show that we can have some better results for TotP than for #P. Firstly, for any instance to any problem in TotP, if the number of solutions is x, we can exactly compute this number in time x*poly(n), where n is the size of the input. In other words, if the number of solutions is polynomial (i.e. small), wecan count them exactly in polynomial time. Secondly if the number of solutions is 2^n/x, we can have a RAS (i.e. arbitrarily small multiplicative error) in time poly(n, x). In other words, if the number of solutions is 2^n/poly(n) (i.e. big), we can have an FPRAS. Thirdly if we combine the above results with the known fact that all problems in #P admit an additive approximation, we get better exponential time algorithmic results for TotP than the corresponding known results for #P. It remains an open question whetherthese results are optimal under a fine grained complexity perspective (i.e. under some assumption analogous to the SETH, which roughly states that SAT needs Θ(2^n) time to be solved).Also after observing that the TotP-complete problem Size-of-Subtree problem is easy to approximate on many instances, in the same chapter we identify a family of trees that we prove to contain difficult instances of the problem.The last issue that this thesis deals with, (in chapter 3), concerns an intuitive belief of many scientists that the only problems in #P that can have an FPRAS belong to TotP, and no counterexamples to this conjecture are known. We prove that this is wrong unless P=RP. In order to show that, we introduce two new complexity classes #RP1 and #RP2, both being counting versions of RP. We also show that the class of problems that admit FPRAS lies between these two classes, and that these classes do not coincide unless NP=RP. Finally, in order to get a more clear picture of the relationships of the above classes with #P and TotP (and some other related classes), we study inclusions between them and present all four possible worlds with respect to the NP v.s. RP, and RP v.s. P questions.

Η κλάση πολυπλοκότητας #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).Ένα σημαντικό θεώρημα που αποδεικνύουμε στο κεφάλαιο 2 είναι ότι το #SAT ανάγεται στο #CM-SAT υπό αναγωγές που διατηρούν την προσεγγισιμότητα. Η δειγματοληψία και η προσεγγιστική μέτρηση πραγματοποιούνται συνήθως με τηχρήση μαρκοβιανών αλυσίδων, οι οποίες πρέπει να είναι εργοδικές (δηλαδή μη αναγώγιμες και απεριοδικές), προκειμένου να λειτουργούν σωστά οι αντίστοιχοι αλγόριθμοι. Ωστόσο, για το #SAT είναι γνωστό ότι δεν μπορούμε να σχεδιάσουμε μη αναγώγιμες μαρκοβιανές αλυσίδες, των οποίων ο χώρος καταστάσεων να είναι το σύνολο ικανοποιητικών αναθέσεων ενός τύπου που δίνεται ως είσοδος, εξαιτίας ενός φαινομένου διασκορπισμού του συνόλου των λύσεων. Αντίθετα, το σύνολο των λύσεων του #CM-SAT, καθώς και του Size-of-Subtree, συνδέεται με έναν συγκεκριμένο τρόπο που επιτρέπει το σχεδιασμό μη αναγώγιμων μαρκοβιανών αλυσίδων.Στο κεφάλαιο 4 σχεδιάζουμε και μελετάμε μερικές μαρκοβιανές αλυσίδες, των οποίων ο χώρος καταστάσεων είναι το σύνολο των λύσεων των παραπάνω προβλημάτων. Αναλύουμε το χρόνο σύγκλισης, τις στάσιμες κατανομές τους και την πολυπλοκότητα υπολογισμού των συντελεστών κανονικοποίησης, όπως και του μεγέθους του στηρίγματος των στάσιμων κατανομών. Τα κύρια αποτελέσματα της μελέτης μας είναι καταρχάς ότι το SAT ανάγεται στον υπολογισμό του συντελεστή κανονικοποίησης των στάσιμων κατανομών κάποιων μαρκοβιανών αλυσίδων, οι οποίες ανήκουν σε μια οικογένεια που σχεδιάζουμε. Με άλλα λόγια, ο υπολογισμός του συντελεστή κανονικοποίησης αυτών των κατανομών είναι δύσκολος εκτός αν NP=P. Δεύτερον, ο συντελεστής κανονικοποίησης αυτών των κατανομών μπορεί να προσεγγιστεί με FPRAS (δηλ. με ένα αυθαίρετα μικρό πολλαπλασιαστικό σφάλμα σε πολυωνυμικό χρόνο).Παρατηρούμε στη συνέχεια ένα ενδιαφέρον φαινόμενο. Στο καφάλαιο 4 για κάθε είσοδο σε ένα πρόβλημα στην TotP θεωρήσαμε δύο διαφορετικές μαρκοβιανές αλυσίδες που συγκλίνουν σε δύο διαφορετικές κατανομές P1, P2, με συντελε-στές κανονικοποίησης Z1,Z2 αντίστοιχα. Στο κεφάλαιο 5 δείχνουμε ότι μπορούμε να γενικεύσουμε τις δύο παραπάνω κατανομές πιθανότητας με ένα ενιαίο μοντέλο P( λ), λ>0; έτσι ώστε P(1) = P1 και P(2) = P2: Αυτό το μοντέλο παρουσιάζει εντελώς διαφορετική συμπεριφορά για λ = 1 και λ = 2: Και για τα δύο λ = 1 και λ = 2, ο υπολογισμός του Z είναι δύσκολος (#P-πλήρης), αλλά για λ = 1 έχουμε• εκθετικό χρόνο σύγκλισης της αντίστοιχης μαρκοβιανής αλυσίδας• αδυναμία ύπαρξης FPRAS για το Z1 εκτός NP = RP.και για λ = 2 έχουμε• πολυωνυμικό χρόνο σύγκλισης της αντίστοιχης μαρκοβιανής αλυσίδας• FPRAS για το Z2.Το ερώτημα που τίθεται είναι τι ισχύει για τις υπόλοιπες τιμές του λ > 0. Σχεδιάζουμε (στο κεφάλαιο 5) μια μαρκοβιανή αλυσίδα, παραμετροποιημένη από το λ, που γενικεύει τις δύο διαφορετικές μαρκοβιανές αλυσίδες που μελετήθηκαν στο κε-φάλαιο 4. Αυτή η μαρκοβιανή αλυσίδα Mλ ακολουθεί τον κανόνα του Metropolis και συγκλίνει στην κατανομή P(λ). Δείχνουμε ότι υπάρχει αλλαγή φάσης ως προς τον χρόνο σύγκλισης της Mλ συναρτήσει του λ. Συγκεκριμένα, υπάρχει μια ασυνεχής μετάβαση από εκθετικό σε πολυωνυμικό χρόνο σύγκλισης για λ που εξαρτάται από το δέντρο. Για το πλήρες δέντρο, όπως και για τα δέντρα που αποτελούν δύσκολα στιγμιότυπα του προβλήματος 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) αφορά στη σχέση της TotP με την κλάση προβλημάτων που επιδέχονται FPRAS. Όπως αναφέραμε ήδη, NP=RP αν και μόνο αν όλα τα προβλήματα στην TotP επιδέχονται FPRAS. Αφου το NP vs. RP είναι ένα από τα σημαντικότερα προβλήματα τηε θεωρητικής πληροφορικής, το ίδιο ισχύει άρα και για το TotP vs. FPRAS, για αυτό και το μελετούμε. Mια διαισθητική πεποίθηση πολλών επιστημόνων είναι ότι τα μόνα προβλήματα στην #Ρ που μπορεί να έχουν FPRAS ανήκουν στην TotP, και δεν υπάρχουν ως τώρα γνωστά αντιπαραδείγματα σε αυτή την εικασία. Αποδεικνύουμε ότι αυτή η πεποίθηση είναι λάθος εκτός εάν P = RP. Προκειμένου να το δείξουμε αυτό, εισάγουμε δύο νέες κλάσεις πολυπλοκότητας #RP1 και #RP2 με τη βοήθεια των οποίων το αποτέλεσμα προκύπτει εύκολα. Δείχνουμε επίσης ότι η κλάση των προβλημάτων που επιδέχονται FPRAS βρίσκεται μεταξύ αυτών των δύο κλάσεων και ότι αυτές οι κλάσεις δεν συμπίπτουν εκτός αν NP = RP. Τέλος, για να αποκτήσουμε μια πιο ξεκάθαρη εικόνα των σχέσεων των παραπάνω κλάσεων με την #P και την TotP (και με μερικές άλλες σχετικές κλάσεις), μελετάμε τους εγκλεισμούς μεταξύ τους και παρουσιάζουμε τους τέσσερις δυνατούς κόσμους σεσχέση με τα προβλήματα NP vs. RP και RP vs. P.