Details
| Original language | English |
|---|---|
| Title of host publication | 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) |
| Editors | Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Pages | 19:1-19:15 |
| Number of pages | 15 |
| Volume | abs/1902.00246 |
| ISBN (electronic) | 9783959771177 |
| Publication status | Published - 20 Aug 2019 |
| Event | 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 - Aachen, Germany Duration: 26 Aug 2019 → 30 Aug 2019 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 138 |
| ISSN (Print) | 1868-8969 |
Abstract
We study descriptive complexity of counting complexity classes in the range from #P to # · NP. A corollary of Fagin’s characterization of NP by existential second-order logic is that #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. In this paper we extend this study to classes beyond #P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of first-order logic in Tarski’s semantics. Our results show that the class # · NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of # · NP and #P, respectively. We also study the function class generated by inclusion logic and relate it to the complexity class TotP ⊆ #P. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean Σ1-formulae is # · NP-complete with respect to Turing reductions as well as complete for the function class generated by dependence logic with respect to first-order reductions.
Keywords
- Counting classes, Descriptive complexity, Finite model theory, Team-based logics
ASJC Scopus subject areas
- Computer Science(all)
- Software
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). ed. / Peter Rossmanith; Pinar Heggernes; Joost-Pieter Katoen. Vol. abs/1902.00246 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. p. 19:1-19:15 19 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 138).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Counting of teams in first-order team logics
AU - Haak, Anselm
AU - Kontinen, Juha
AU - Müller, Fabian
AU - Vollmer, Heribert
AU - Yang, Fan
N1 - Funding Information: Funding Anselm Haak, Fabian Müller, Heribert Vollmer: Supported by DFG VO 630/8-1 and DAAD grant 57348395. Juha Kontinen, Fan Yang: Supported by grants 308712 and 308099 of the Academy of Finland. We thank the anonymous referees for helpful comments.
PY - 2019/8/20
Y1 - 2019/8/20
N2 - We study descriptive complexity of counting complexity classes in the range from #P to # · NP. A corollary of Fagin’s characterization of NP by existential second-order logic is that #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. In this paper we extend this study to classes beyond #P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of first-order logic in Tarski’s semantics. Our results show that the class # · NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of # · NP and #P, respectively. We also study the function class generated by inclusion logic and relate it to the complexity class TotP ⊆ #P. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean Σ1-formulae is # · NP-complete with respect to Turing reductions as well as complete for the function class generated by dependence logic with respect to first-order reductions.
AB - We study descriptive complexity of counting complexity classes in the range from #P to # · NP. A corollary of Fagin’s characterization of NP by existential second-order logic is that #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. In this paper we extend this study to classes beyond #P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of first-order logic in Tarski’s semantics. Our results show that the class # · NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of # · NP and #P, respectively. We also study the function class generated by inclusion logic and relate it to the complexity class TotP ⊆ #P. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean Σ1-formulae is # · NP-complete with respect to Turing reductions as well as complete for the function class generated by dependence logic with respect to first-order reductions.
KW - Counting classes
KW - Descriptive complexity
KW - Finite model theory
KW - Team-based logics
UR - http://www.scopus.com/inward/record.url?scp=85071755751&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1902.00246
DO - 10.48550/arXiv.1902.00246
M3 - Conference contribution
AN - SCOPUS:85071755751
VL - abs/1902.00246
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 19:1-19:15
BT - 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
A2 - Rossmanith, Peter
A2 - Heggernes, Pinar
A2 - Katoen, Joost-Pieter
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019
Y2 - 26 August 2019 through 30 August 2019
ER -