@article{61874,
  abstract     = {{<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>}},
  author       = {{Haak, Anselm and Kontinen, Juha and Müller, Fabian and Vollmer, Heribert and Yang, Fan}},
  issn         = {{1529-3785}},
  journal      = {{ACM Transactions on Computational Logic}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  title        = {{{Counting of Teams in First-Order Team Logics}}},
  doi          = {{10.1145/3771721}},
  year         = {{2025}},
}

@article{54577,
  abstract     = {{<jats:p>Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this article, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Creignou et al. 2014 and Parson et al., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: First, we consider all possible propositional fragments of the problem within Schaefer’s framework (STOC 1978) and then study different parameterizations for each of the fragments. We identify a list of reasonable structural parameters (size of the claim, support, knowledge base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (para-NP and beyond).</jats:p>}},
  author       = {{Mahmood, Yasir and Meier, Arne and Schmidt, Johannes}},
  issn         = {{1529-3785}},
  journal      = {{ACM Transactions on Computational Logic}},
  number       = {{3}},
  pages        = {{1--25}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  title        = {{{Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework}}},
  doi          = {{10.1145/3582499}},
  volume       = {{24}},
  year         = {{2023}},
}