Summary:
In this thesis we study dichotomy theorems mainly of counting problems. A
dichotomy theorem for a class of problems, in computational complexity, is a
complete classification of the problems of this class in computationally easy
and computationally hard problems, without intermediate problems. Due to
Ladner's theorem we cannot find a dichotomy 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 begin with the framework of
the decision version of constraint satifaction problems (CSP) and then we study
the classes of graph homomorphisms problems, of counting constraint
satisfaction problems (#CSP) and of Holant problems. Finally, we will make a
brief introduction to holographic algorithms, a special type of polynomial-time
algorithms for counting problems.
Keywords:
Dichotomy, Constraint Satisfaction Problem, Graph Homomorphisms, Holant Problems, Holographic Algorithms
