Back to search

National Technical University of Athens (NTUA)

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

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/52239

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Chalki, Angeliki; Χαλκή, Αγγελική. On structural and descriptive complexity of hard counting problems the decision version of which is easy. National Technical University of Athens (NTUA), 2022. http://hdl.handle.net/10442/hedi/52239