Complezity of Counting the Optimal Solutions

摘要：

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 #·ΠkP 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 optimizar tion 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

作者: Miki Hermann Reinhard Pichler

作者单位: LIX (CNRS, UMR 7161), Ecole Polytechnique, 91128 Palaiseau,Prance Institut für Informationssysteme, Technische Universitat Wien, A-1040 Wien, Austria

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 149-159

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）