Arenas, Marcelo and Muñoz, Martin and Riveros, Cristian - Descriptive Complexity for Counting Complexity Classes

lmcs:4493 - Logical Methods in Computer Science, February 10, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:9)2020
Descriptive Complexity for Counting Complexity Classes

Authors: Arenas, Marcelo and Muñoz, Martin and Riveros, Cristian

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.


Volume: Volume 16, Issue 1
Published on: February 10, 2020
Submitted on: May 9, 2018
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 131 times.
This article's PDF has been downloaded 112 times.