-----------------------------------------------------------------------
                   B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                     Monday, September 10, 11:00 AM 
                       (Coffee served at 10:45AM)
                         Seminar Room / MCS 135


			"Functions That Count"

	                by Prof. Stathis Zachos


			        Abstract

   Traditional Complexity Classes (P, NP, PH,...) contain decision
problems, computed by TM acceptors. TMs can of course compute functions as
well (FP, FNP,...).  Here we discuss counting functions: their values are
numbers (#) of paths of TM acceptors. We survey complexity classes of
counting functions (#P, #PH,...) and discuss reduction relations (Cook,
Karp) 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 corresponding counting problems which are
(Cook- and Karp-) complete in #P. But also #PERFECT MATCHINGS is
Cook-complete for all the above counting classes, which is surprising as
PERFECT MATCHING is actually in P.  Thus, Cook- (even Cook[1]-) reductions
blur structural differences between counting complexity classes. We define
and study a new complexity class TotP (# of all paths of a PNTM) for which
#PERFECT MATCHINGS is Cook- but probably also Karp-complete, and which
contains only those counting functions of #P that have easy corresponding
decision problems (in P) and a self-reducibility property.



Host: George Kollios
-------------------------------------------------------------------------