Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) |
| Herausgeber/-innen | Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen |
| Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Seiten | 19:1-19:15 |
| Seitenumfang | 15 |
| Band | abs/1902.00246 |
| ISBN (elektronisch) | 9783959771177 |
| Publikationsstatus | Veröffentlicht - 20 Aug. 2019 |
| Veranstaltung | 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 - Aachen, Deutschland Dauer: 26 Aug. 2019 → 30 Aug. 2019 |
Publikationsreihe
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Band | 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.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Software
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Hrsg. / Peter Rossmanith; Pinar Heggernes; Joost-Pieter Katoen. Band abs/1902.00246 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. S. 19:1-19:15 19 (Leibniz International Proceedings in Informatics, LIPIcs; Band 138).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › 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 -