The Computer Science Colloquium

STATHIS ZACHOS
(Computer Science, CUNY)

"Functions that Count"

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 discuss 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 and other #P-complete problems belong to, and therefore are 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.


Biographical information:
Zachos received his Ph.D. from the ETHZ (Swiss Federal Institute of Technology Zurich) in Mathematics (and Computer Science), in 1978. He was a visiting scientist at MIT in 1982 and 1983. Zachos works in the area of Computational Complexity. One of his important contributions, using Interactive Proof Systems and Probabilistic Quantifiers, is that the Graph Isomorphism Problem is not likely to be NP-complete (joint with R. Boppana, J. Hastad). Graph Isomorphism is one of the very few celebrated problems of NP that have not been shown yet to be either NP-Complete or in P. Zachos' most influential work was introducing and proving properties of the class parity-P (with C. Papadimitriou). He also introduced Probabilistic Quantifiers and Alternations of Probabilistic Quantifiers to uniformly describe various Complexity Classes, as well as Interactive Proof Systems and Probabilistic Games. His current interests include Probabilistic and Functional Complexity Classes, Combinatory Algebras as a foundation to Theory of Computations, the interconnections of Cryptographic Techniques and Computational Complexity, as well as Algorithms for Graph Problems. He recently co-organized International Conferences in Greece: STOC, ICALP, PLS, in 2001 on Crete; ASL European Summer Meeting and PLS in 2005; and ACAC (Athens Colloquium on Algorithms and Complexity) in 2006 in Athens.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc., and Netlogic, Inc.