# Corelab Seminar

*2008-2009*

### Andreas Göbel (NTUA)

*On the connection between interval size functions and path counting*

**Abstract.** We investigate the complexity of hard counting problems that belong
to the class #P but have easy decision version; several
well-known problems such as #PERFECT MATCHINGS, #DNFSAT share this property. We
focus on classes of such problems which emerged through two
disparate approaches: one taken by Hemaspaandra et al. [HHKW07] who
defined classes of functions that count the size of intervals of ordered
strings, and one followed by Kiayias et al. [KPSZ98] who defined the class
TotP, that consists of functions that count the total number of
paths of NP
computations and contains #PERFECT MATCHINGS, #DNFSAT as shown by Pagourtzis and
Zachos [PZ06]. We provide inclusion and separation relations between TotP
and interval size counting classes, by means of new classes that we define in
this work. Our results imply that many known #P-complete problems with
easy decision are contained in the classes defined in [HHKW07] but are unlikely
to be complete for these classes under certain types of reductions. We also
define a new class of interval size functions which strictly contains
FP and is
strictly contained in TotP under reasonable complexity-theoretic
assumptions.
We show that this new class contains some hard counting problems.

(joint work with E. Bampas, A. Pagourtzis, A. Tentes)