Descriptive Complexity for counting complexity classes
Descriptive Complexity for counting complexity classes
复制标题
用于计算复杂性类别的描述性复杂性
DOI：
10.23638/lmcs-16(1:9)2020
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Cristian Riveros
中科院分区：
文献类型：
--
作者：
M. Arenas;Martin Muñoz;Cristian Riveros
描述性复杂性在根据某些逻辑中可定义的属性来描述决策问题的复杂性类别方面非常成功。然而，用于计算复杂性类别的描述性复杂性（例如 FP 和 #P）尚未得到系统研究，并且不像决策对应物那样发达。在本文中，我们提出了一个基于加权逻辑的框架来解决这个问题。具体来说，通过关注自然数，我们获得了一种称为定量二阶逻辑 (QSO) 的逻辑，并展示了如何使用它的一些片段来捕获基本的计数复杂性类别，例如 FP、#P 和 FPSPACE 等。我们还使用 QSO 在 #P 内定义层次结构，识别具有良好闭包和近似属性的计数复杂性类，并承认自然完整的问题。最后，我们向 QSO 添加递归，并展示此扩展如何自然地捕获较低计数复杂性的类，例如 #L。
Descriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive complexity for counting complexity classes, such as FP and #P, has not been systematically studied, and it is not as developed as its decision counterpart. In this paper, we propose a framework based on Weighted Logics to address this issue. Specifically, by focusing on the natural numbers we obtain a logic called Quantitative Second Order Logics (QSO), and show how some of its fragments can be used to capture fundamental counting complexity classes such as FP, #P and FPSPACE, among others. We also use QSO to define a hierarchy inside #P, identifying counting complexity classes with good closure and approximation properties, and which admit natural complete problems. Finally, we add recursion to QSO, and show how this extension naturally captures lower counting complexity classes such as #L.
DOI：
10.1016/j.jcss.2020.04.002
发表时间：
2021
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
A. Durand;A. Haak;J. Kontinen;H. Vollmer
通讯作者：
H. Vollmer