Back to search

National Technical University of Athens (NTUA)

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

Abstract

dc:description

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.

Degree

thesis:*
Grantor dc:publisher
National Technical University of Athens (NTUA)
Year dc:date
2018

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Bakali, Eleni
  • Μπακάλη, Ελένη

Subjects

dc:subject × 26

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/45002

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

Bakali, Eleni; Μπακάλη, Ελένη. Ιδιότητες συναρτήσεων μέτρησης πλήθους λύσεων σε προβλήματα με εύκολη απόφαση ύπαρξης λύσης: πληρότητα, προσεγγισιμότητα, μαρκοβιανές αλυσίδες, αλλαγές φάσης. National Technical University of Athens (NTUA), 2018. http://hdl.handle.net/10442/hedi/45002