论文标题
#P以下的硬计数类的特征和近似性
Characterizations and approximability of hard counting classes below #P
论文作者
论文摘要
研究复杂性研究的一个重要目标是了解哪些计数问题是可能的。在此任务中，复杂性类TOTP是#P的硬式子类，至关重要，因为它包含具有简单决策版本的可自我还原的计数问题，因此有资格近似。确实，到目前为止，大多数已知的问题都承认FPRA属于这一班。 描述性复杂性社区最近提出的一个公开问题是找到TOTP的逻辑表征和TOTP的强大子类的逻辑表征。在这项工作中，我们在描述性复杂性方面定义了TOTP的两个子类，因为它们具有自然的完整问题，它们都是可靠的，这些问题是根据布尔公式的满意度定义的。 然后，我们探讨了近似计数问题和TOTP的类别之间的关系。 我们证明，只有当NP $ \ neq $ rp和fpras $ \ nsubseteq $ totp当RP = P以外，我们才证明totp $ \ nsubseteq $ fpras，只有当时我们介绍了两个辅助类，这些辅助类都可以看作是RP的计数版本。我们进一步表明 FPRA位于这些类别之一和BPP的计数版本之间。 最后，我们在本文中有关NP与RP与P问题的不同猜想中所定义或讨论的所有类别中的包含物提供了完整的描述。
An important objective of research in counting complexity is to understand which counting problems are approximable. In this quest, the complexity class TotP, a hard subclass of #P, is of key importance, as it contains self-reducible counting problems with easy decision version, thus eligible to be approximable. Indeed, most problems known so far to admit an fpras fall into this class. An open question raised recently by the community of descriptive complexity is to find a logical characterization of TotP and of robust subclasses of TotP. In this work we define two subclasses of TotP, in terms of descriptive complexity, both of which are robust in the sense that they have natural complete problems, which are defined in terms of satisfiability of Boolean formulae. We then explore the relationship between the class of approximable counting problems and TotP. We prove that TotP $\nsubseteq$ FPRAS if and only if NP $\neq$ RP and FPRAS $\nsubseteq$ TotP unless RP = P. To this end we introduce two ancillary classes that can both be seen as counting versions of RP. We further show that FPRAS lies between one of these classes and a counting version of BPP. Finally, we provide a complete picture of inclusions among all the classes defined or discussed in this paper with respect to different conjectures about the NP vs. RP vs. P questions.
