COLLOQUIUM
         Computer Science Department, Boston University

Speaker: Prof. Stathis Zachos
         Brooklyn College of CUNY and NTUA 

Title: The Complexity of Counting Functions with Easy Decision Version

Date:  September 13, 2004
Time:  11am
Place: MCS 135 (for directions, see www.cs.bu.edu/colloquium)

Abstract:

Traditional Complexity Classes (P, NP, PH,...) contain decision
problems, computed by TM acceptors. TMs can of course compute
functions as well (FP, FNP,...).  In this talk we discuss
counting functions: their values are numbers of paths of TM
acceptors.  We survey complexity classes of counting functions
(#P, #PH,...) and discuss (Cook and Karp) reduction relations
between such function classes. Valiant(1979) introduced #P and
Toda(1991) showed that #P is at least as hard as the whole PH.

NP-complete problems have counting versions which are #P-complete
w.r.t. Cook (and Karp) reductions.  On the other hand #PERFECT
MATCHINGS is also Cook-complete for #P, which is surprising as
PERFECT MATCHING is actually in P (which implies that #PERFECT
MATCHINGS cannot be Karp-complete for \#P).  Thus, Cook(even
Cook[1]) reductions blur structural differences between counting
complexity classes.

Here we define and study two new complexity classes: #PE
(functions of #P with easy decision version) and TotP (# of all
paths of a PNTM).  We investigate the relation between them.  We
show that #PERFECT MATCHINGS belongs to and therefore is
Cook-complete for both these classes.  Our main result is that
TotP is exactly the closure w.r.t. Karp reduction of
self-reducible functions of #PE.

Host: George Kollios (www.cs.bu.edu/~gkollios)