National Technical University of Athens (NTUA)
On structural and descriptive complexity of hard counting problems the decision version of which is easy
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Chalki, Angeliki
- Χαλκή, Αγγελική
Subjects
dc:subject × 18- Υπολογιστική πολυπλοκότητα
- Περιγραφική πολυπλοκότητα
- Προβλήματα μέτρησης λύσεων
- Εύκολο πρόβλημα απόφασης
- Computational complexity
- Descriptive complexity
- Counting problems
- Easy decision version
- Μαθηματικά
- Φυσικές Επιστήμες
- Μαθηματική λογική
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμη ηλεκτρονικών υπολογιστών και Πληροφορική, άλλοι τομείς
- Mathematics
- Natural Sciences
- Logic
- Computer and Information Sciences
- Computer and Information sciences, miscellaneous
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/52239