ECCC-Report TR08-044https://eccc.weizmann.ac.il/report/2008/044Comments and Revisions published for TR08-044en-usWed, 16 Apr 2008 22:02:33 +0300
Paper TR08-044
| Complexity of Counting the Optimal Solutions |
Miki Hermann,
Reinhard Pichler
https://eccc.weizmann.ac.il/report/2008/044Following 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.
Wed, 16 Apr 2008 22:02:33 +0300https://eccc.weizmann.ac.il/report/2008/044