Title: Complexity of Counting the Optimal Solutions.
Abstract: 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 #@?@PkP 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 #@?OptkP and #@?OptkP[logn] with k>=1. We prove several important properties of these new classes, like closure properties and the relationship with the #@?@PkP-classes. Moreover, we establish the completeness of several natural counting complexity problems for these new classes.
Publication Year: 2008
Publication Date: 2008-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot