一句话：提出基于加权逻辑的 QSO，统一刻画 FP、#P、FPSPACE 等计数复杂性类并引入 #P 内层级。
描述复杂性已成功用逻辑可定义性刻画判定复杂性类，但计数复杂性类如 FP 与 #P 的系统性描述复杂性研究仍缺乏。本文提出基于 Weighted Logics 的框架，聚焦自然数得到 Quantitative Second Order Logics (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 原文 · arXiv · PDF（开放获取） · DBLP
@article{ArenasMR17,
title = {Descriptive Complexity for Counting Complexity Classes},
author = {Marcelo Arenas and Martin Muñoz and Cristian Riveros},
journal = {Logical Methods in Computer Science},
volume = {Volume 16, Issue 1},
year = {2020},
doi = {10.23638/lmcs-16(1:9)2020}
}