A logical characterization of the counting hierarchy
A logical characterization of the counting hierarchy
复制标题
计数层次的逻辑特征
DOI：
10.1145/1459010.1459017
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
J. Kontinen
中科院分区：
文献类型：
--
作者：
J. Kontinen
在这篇文章中，我们给出了计数层次的逻辑特征。计数层次是多项式层次的类似物，构建块是概率多项式时间PP而不是NP。我们表明，扩展的一阶逻辑的二阶多数量词的所有arities准确地描述了计数层次中的问题。我们还考虑扩展到一般的比例量词<i>Q<sup>K</sup><sub>R</sub></i>解释为“超过一个<i>r</i>-分数的<i>k</i>元关系”的特性。我们证明了这个结果<i>对s</i>/2<sup><i>m</i></sup>形式的有理数成立，但对任何其他0 <<i>r</i>< 1，相应的逻辑满足0-1律。
In this article we give a logical characterization of the counting hierarchy. The counting hierarchy is the analogue of the polynomial hierarchy, the building block being Probabilistic polynomial time PP instead of NP. We show that the extension of first-order logic by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We also consider extending the characterization to general proportional quantifiers <i>Q<sup>k</sup><sub>r</sub></i> interpreted as “more than an <i>r</i>-fraction of <i>k</i>-ary relations”. We show that the result holds for rational numbers of the form <i>s</i>/2<sup><i>m</i></sup> but for any other 0 < <i>r</i> < 1 the corresponding logic satisfies the 0-1 law.