On structural and descriptive complexity of hard counting problems the decision version of which is easy

Abstract

The complexity class #P introduced by Valiant, contains the counting versions of NP problems. We focus on #PE, the class of #P functions the decision version of which is in P. In fact, we are mostly interested in a subclass of #PE, namely TotP, which contains all self-reducible #PE functions. TotP has already three interesting characterizations and it is a robust class; it has nice closure properties and natural complete problems as we will discuss in this thesis.We study the class TotP from different angles: 1) We examine the TotP-complete problems under parsimonious reductions. In specific, we provide some lower bound results for the exponential-time complexity of the problem Size-of-subtree which has been introduced by Knuth as the problem of estimating the size of a backtracking procedure's tree and has been studied from many perspectives. These results are under variants of ETH. 2) Efficient and exact counting is very rare, so the main research interest in this area is to classify counting problems with respect to their approximability and design approximation algorithms for those that can be approximated. In this quest, properties of problems in TotP are significant. We discuss the relationship of TotP with the class of approximable counting problems, namely FPRAS, and we define three counting problems, that each has a decision version in RP, which is not known to lie in P. We prove that one of them, namely #NonZerosForPIT, has an fpras.3) We examine the problem #Exact Matchings, which is one of the aforementioned problems with a decision version in RP, with respect to exact and approximate computation. This problem is a generalization of counting perfect matchings in graphs that contain both black and red edges. 4) Then we turn our attention to logical characterizations of classes of counting problems. We build upon previous work in the area of descriptive complexity for counting problems. We give logical characterizations of two robust subclasses of TotP and determine their relationship with FPRAS. Most importantly, we provide a logical characterization of TotP, which was an open question in the area of descriptive complexity. To express self-reducibility, we add recursion on functions over second-order variables to the logic QSO introduced by Arenas et al, which, we believe, is of independent interest. 5) We also investigate the power of counting the total number of paths of an NPTM. This interest arises from the definition of TotP: it contains functions that count the number of all paths of NPTMs. This investigation led us to the study of decision classes and problems defined via TotP problems, such as the problem DiffPerfMatch=1, where on input two graphs we have to decide whether the difference between the number of perfect matchings in these graphs is equal to 0 or to 1.

Η κλάση πολυπλοκότητας #P, την οποία εισήγαγε ο Valiant, περιέχει τις μετρητικές εκδοχές προβλημάτων της κλάσης NP. Σε αυτή τη διατριβή, εστιάζουμε στη #PE, την κλάση των συναρτήσεων της #P που έχουν αντίστοιχο πρόβλημα απόφασης στην P. Kυρίως μας ενδιαφέρει η υποκλάση της #PE, που ονομάζεται TotP και περιέχει συναρτήσεις της #PE που είναι επιπλέον αυτοαναγώγιμες. Η TotP έχει τρεις ενδιαφέροντες χαρακτηρισμούς και είναι μια εύρωστη κλάση, δηλ. έχει χρήσιμες ιδιότητες κλειστότητας και φυσικά πλήρη προβλήματα όπως θα συζητήσουμε.Μελετάμε την TotP από διαφορετικές οπτικές γωνίες: 1) Εξετάζουμε τα TotP-πλήρη προβλήματα ως προς φειδωλές αναγωγές, δηλ. τα πιο δύσκολα και αντιπροσωπευτικά προβλήματα της κλάσης TotP. Aποδεικνύουμε ότι το πρόβλημα Size-of-subtree δεν μπορεί να λυθεί σε υποεκθετικό χρόνο αν ισχύουν εκδοχές της Υπόθεσης Εκθετικού Χρόνου (ETH). 2) Η ακριβής και αποδοτική επίλυση ενός μετρητικού προβλήματος είναι πολύ σπάνια. Υπάρχει έντονο ερευνητικό ενδιαφέρον για την ταξινόμηση των μετρητικών προβλημάτων ως προς τη δυνατότητα επίλυσης τους με τη χρήση προσεγγιστικών αλγορίθμων. Σε αυτήν την αναζήτηση, οι ιδιότητες των προβλημάτων της TotP είναι σημαντικές. Αναφερόμαστε στη σχέση της κλάσης TotP με την κλάση των προσεγγίσιμων μετρητικών προβλημάτων. Ορίζουμε τρία προβλήματα, καθε ένα από τα οποία έχει αντίστοιχο πρόβλημα απόφασης στην κλάση RP, για το οποίο δε γνωρίζουμε αν ανήκει στην P. Δείχνουμε ότι ένα από αυτά, το πρόβλημα #NonZerosForPIT, είναι προσεγγίσιμο. 3) Εξετάζουμε το πρόβλημα #Exact Matchings, το οποίο επίσης έχει πρόβλημα απόφασης στην κλάση RP, ως προς τον ακριβή υπολογισμό του και την προσεγγισιμότητά του. Το πρόβλημα αυτό γενικεύει τη μέτρηση τέλειων ταιριασμάτων σε γράφους που περιέχουν μαύρες και κόκκινες ακμές. 4) Δίνουμε λογικούς χαρακτηρισμούς κλάσεων μετρητικών προβλημάτων. Αρχικά, δύο εύρωστων υποκλάσεων της TotP και προσδιορίζουμε τη σχέση τους με την κλάση FPRAS. Θεωρούμε ότι πιο σημαντικό βήμα είναι ότι παρέχουμε ένα λογικό χαρακτηρισμό της TotP. Για να εκφράσουμε την αυτοαναγωγιμότητα των προβλημάτων της TotP, προσθέτουμε αναδρομή ορισμένη σε συναρτήσεις με ορίσματα δευτεροβάθμιες μεταβλητές, στη λογική QSO, το οποίο θεωρούμε ότι έχει ανεξάρτητο ενδιαφέρον. 5) Διερευνούμε την ισχύ που μας προσφέρει η μέτρηση όλων των μονοπατιών κάποιας NPTM (μη ντετερμινιστικής μηχανής Turing πολυωνυμικού χρόνου). Αυτό το ενδιαφέρον προκύπτει από τον ορισμό της TotP: περιέχει συναρτήσεις που μετράνε το πλήθος όλων των μονοπατιών NPTMs. H διερεύνηση αυτή μας οδήγησε στη μελέτη κλάσεων αλλά και συγκεκριμένων προβλημάτων απόφασης που ορίζονται μέσω προβλημάτων της TotP, όπως για παράδειγμα το πρόβλημα DiffPerfMatch=1, που δεδομένων δύο γράφων πρέπει να αποφασίσουμε αν η διαφορά του πλήθους των τέλειων ταιριασμάτων σ'αυτούς τους γράφους είναι 0 ή 1.