Descriptive Complexity for Counting Complexity Classes
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 dev...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2020-02-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/4493/pdf |
| _version_ | 1797268582283870208 |
|---|---|
| author | Marcelo Arenas Martin Muñoz Cristian Riveros |
| author_facet | Marcelo Arenas Martin Muñoz Cristian Riveros |
| author_sort | Marcelo Arenas |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:34:46Z |
| format | Article |
| id | doaj.art-b078bc5610bf4922a69b9f7a3e3fd877 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:34:46Z |
| publishDate | 2020-02-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-b078bc5610bf4922a69b9f7a3e3fd8772024-03-08T10:29:26ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742020-02-01Volume 16, Issue 110.23638/LMCS-16(1:9)20204493Descriptive Complexity for Counting Complexity ClassesMarcelo ArenasMartin MuñozCristian RiverosDescriptive 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.https://lmcs.episciences.org/4493/pdfcomputer science - logic in computer science |
| spellingShingle | Marcelo Arenas Martin Muñoz Cristian Riveros Descriptive Complexity for Counting Complexity Classes Logical Methods in Computer Science computer science - logic in computer science |
| title | Descriptive Complexity for Counting Complexity Classes |
| title_full | Descriptive Complexity for Counting Complexity Classes |
| title_fullStr | Descriptive Complexity for Counting Complexity Classes |
| title_full_unstemmed | Descriptive Complexity for Counting Complexity Classes |
| title_short | Descriptive Complexity for Counting Complexity Classes |
| title_sort | descriptive complexity for counting complexity classes |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/4493/pdf |
| work_keys_str_mv | AT marceloarenas descriptivecomplexityforcountingcomplexityclasses AT martinmunoz descriptivecomplexityforcountingcomplexityclasses AT cristianriveros descriptivecomplexityforcountingcomplexityclasses |