Counting of Teams in First-Order Team Logics

<jats:p> We study descriptive complexity of counting complexity classes in the range from #P to <jats:inline-formula content-type="math/tex"> <jats:tex-math notation="LaTeX" version="MathJax">\({\text{#}\!\cdot\!\text{NP}}\)</jats:tex-math> </jats:inline-formula> . The proof of Fagin’s characterization of NP by existential second-order logic generalizes to the counting setting in the following sense: The class #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. This was first observed by Saluja et al. (1995). 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 <jats:inline-formula content-type="math/tex"> <jats:tex-math notation="LaTeX" version="MathJax">\({\text{#}\!\cdot\!\text{NP}}\)</jats:tex-math> </jats:inline-formula> can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of <jats:inline-formula content-type="math/tex"> <jats:tex-math notation="LaTeX" version="MathJax">\({\text{#}\!\cdot\!\text{NP}}\)</jats:tex-math> </jats:inline-formula> and #P , respectively. We further relate the class obtained from inclusion logic to the complexity class <jats:inline-formula content-type="math/tex"> <jats:tex-math notation="LaTeX" version="MathJax">\({\text{TotP}} \subseteq{\text{#P}}\)</jats:tex-math> </jats:inline-formula> . </jats:p>