Supervisors info:
Καθηγητής Ευστάθιος Ζάχος (επιβλέπων), Επικ. Καθηγητής Αριστείδης Παγουρτζής, Λέκτορας Δημήτρης Φωτάκης
Summary:
This thesis is a survey of dichotomy theorems for computational problems,
focusing in counting problems. A dichotomy theorem in computational
complexity, is a complete classification of the members of a class of problems,
in computationally easy and computationally hard, with the set of problems of
intermediate
complexity being empty. Due to Ladner's theorem we cannot find a dichotomy
theorem for the whole classes NP and #P, however there are large subclasses of
NP (#P),
that model many "natural" problems, for which dichotomy theorems exist.
We continue with the decision version of constraint satisfaction problems
(CSP), a class of problems in NP, for which Ladner's theorem doesn't apply. We
obtain a
dichotomy theorem for some special cases of CSP. We then focus on counting
problems presenting the following frameworks: graph homomorphisms, counting
constraint
satisfaction (#CSP) and Holant problems; we provide the known dichotomies for
these frameworks.
In the last and main chapter of this thesis we relax the requirement of exact
computation, and settle in approximating the problems. We present the known
cassification theorems
for cases of #CSP. Many questions in terms of approximate counting problems
remain open.
The appendix introduces a recent technique for obtaining exact polynomial-time
algorithms for counting problems, namely the holographic algorithms.
Keywords:
Computational Complexity, Counting Complexity, Dichotomy Theorems, Approximation Algorithms, Constraint Satisfaction Problem
