TR08-044 Authors: Miki Hermann, Reinhard Pichler

Publication: 16th April 2008 22:02

Downloads: 2092

Keywords:

Following the approach of Hemaspaandra and Vollmer, we can define

counting complexity classes #.C for any complexity class C of decision

problems. In particular, the classes #.Pi_{k}P with k >= 1

corresponding to all levels of the polynomial hierarchy have thus been

studied. However, for a large variety of counting problems arising

from optimization problems, a precise complexity classification turns

out to be impossible with these classes. In order to remedy this

unsatisfactory situation, we introduce a hierarchy of new counting

complexity classes #.Opt_{k}P and #.Opt_{k}P[log n] with k >= 1. We

prove several important properties of these new classes, like closure

properties and the relationship with the #.Pi_{k}P-classes. Moreover,

we establish the completeness of several natural counting complexity

problems for these new classes.