2026-07-25T23:26:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10963 2024-03-06T10:46:55Z ddc:004 open_access

Counting of Teams in First-Order Team Logics Haak, Anselm Kontinen, Juha Müller, Fabian Vollmer, Heribert Yang, Fan team-based logics counting classes finite model theory descriptive complexity 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, which is a subclass of #P. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean Sigma_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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anselm Haak and Juha Kontinen and Fabian Müller and Heribert Vollmer and Fan Yang 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.19 urn:nbn:de:0030-drops-109634 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.19 eng https://creativecommons.org/licenses/by/3.0/legalcode