🚀 go-pugleaf

                         UNIVERSITY OF ROCHESTER
                       Computer Science Department   

                                SEMINAR
                           November 23, 1992
                      209 Computer Studies Building
                               11:00 A.M.

                                Speaker
                          MITSUNORI OGIWARA
               University of Electro-Communications, Tokyo



                        How Hard is Counting?

In 1979, Valiant introduced #P as a class of functions that count the number of
accepting computation paths of NP machines; equivalently, a class of functions
that count the number of solutions
in NP problems.
By applying simple thresholds to #P,
various complexity classes called `counting classes'
have been introduced.
As typical classes among them, we have PP, C_=P, and \oplus P,
which are defined by thresholds
`at least a half of the paths are accepting,'
`exactly a half of the paths are accepting,' and
`an odd number of paths are accepting,' respectively.
Recently, Toda proved that PH (the polynomial-time hierarchy)
is polynomial-time reducible to PP,
thereby showing that `counting' has a power to capture even PH.
This leaves us a question ``How strong is the power of counting?''
I have been working on the question along the following
four basic directions.


1.	{\em How are counting classes different from each other?}
	It is widely believed that the above counting classes are
	all different. If so, what are the properties that a counting
	class $C$ possesses and that a counting class $D$ does not
	seem to possess?

2.	{\em What are complete problems for counting classes?}
	Complete problems help us to develop our intuition on
	how complex a complexity class is.
	What type of problems are complete for counting classes
	and for related classess?

3.	{\em Is PH characterized by `counting'?}
	Can we extend Toda's result to show that there is
	a threshold that, applied to #P functions,
	completely characterizes PH?

4.	{\em What properties do #P possess?}
	It is well-known that there are many operations \tau, such as
	addition and multiplication, such that \tau applied to
	#P functions is also computable in #P.
	Is every operation defined over #P computable within
	#P?  If not, what are the `hardness' operations?

This talk will summarize the research I have done along the above four
directions.