home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / wny / seminar / 62 < prev    next >
Encoding:
Text File  |  1992-11-19  |  2.7 KB  |  77 lines
  1. Newsgroups: wny.seminar,cs.seminar
  2. Path: sparky!uunet!psinntp!isc-newsserver!rit!rochester!pat
  3. From: pat@cs.rochester.edu
  4. Subject: U of Rochester Seminar
  5. Message-ID: <9211181656.AA04541@slate.cs.rochester.edu>
  6. Sender: pat@cs.rochester.edu (Pat Marshall)
  7. Organization: Computer Science Department University of Rochester
  8. Distribution: wny
  9. Date: Wed, 18 Nov 92 11:56:30 -0500
  10. Lines: 65
  11.  
  12.                          UNIVERSITY OF ROCHESTER
  13.                        Computer Science Department   
  14.  
  15.                                 SEMINAR
  16.                            November 23, 1992
  17.                       209 Computer Studies Building
  18.                                11:00 A.M.
  19.  
  20.                                 Speaker
  21.                           MITSUNORI OGIWARA
  22.                University of Electro-Communications, Tokyo
  23.  
  24.  
  25.  
  26.                         How Hard is Counting?
  27.  
  28. In 1979, Valiant introduced #P as a class of functions that count the number of
  29. accepting computation paths of NP machines; equivalently, a class of functions
  30. that count the number of solutions
  31. in NP problems.
  32. By applying simple thresholds to #P,
  33. various complexity classes called `counting classes'
  34. have been introduced.
  35. As typical classes among them, we have PP, C_=P, and \oplus P,
  36. which are defined by thresholds
  37. `at least a half of the paths are accepting,'
  38. `exactly a half of the paths are accepting,' and
  39. `an odd number of paths are accepting,' respectively.
  40. Recently, Toda proved that PH (the polynomial-time hierarchy)
  41. is polynomial-time reducible to PP,
  42. thereby showing that `counting' has a power to capture even PH.
  43. This leaves us a question ``How strong is the power of counting?''
  44. I have been working on the question along the following
  45. four basic directions.
  46.  
  47.  
  48. 1.    {\em How are counting classes different from each other?}
  49.     It is widely believed that the above counting classes are
  50.     all different. If so, what are the properties that a counting
  51.     class $C$ possesses and that a counting class $D$ does not
  52.     seem to possess?
  53.  
  54. 2.    {\em What are complete problems for counting classes?}
  55.     Complete problems help us to develop our intuition on
  56.     how complex a complexity class is.
  57.     What type of problems are complete for counting classes
  58.     and for related classess?
  59.  
  60. 3.    {\em Is PH characterized by `counting'?}
  61.     Can we extend Toda's result to show that there is
  62.     a threshold that, applied to #P functions,
  63.     completely characterizes PH?
  64.  
  65. 4.    {\em What properties do #P possess?}
  66.     It is well-known that there are many operations \tau, such as
  67.     addition and multiplication, such that \tau applied to
  68.     #P functions is also computable in #P.
  69.     Is every operation defined over #P computable within
  70.     #P?  If not, what are the `hardness' operations?
  71.  
  72. This talk will summarize the research I have done along the above four
  73. directions.
  74.  
  75.  
  76.  
  77.