### Abstract

We study descriptive complexity of counting complexity classes in the range from $\#$P to $\#\cdot$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 FO in Tarski's semantics. Our results show that the class $\#\cdot$NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of $\#\cdot$NP and $\#$P , respectively. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean $\Sigma_1$-formulae is $\#\cdot$NP-complete as well as complete for the function class generated by dependence logic.

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 |

Number of pages | 15 |

Volume | 138 |

Publication date | Aug 2019 |

Pages | 19:1-19:15 |

ISBN (Electronic) | 978-3-95977-117-7 |

DOIs | |

Publication status | Published - Aug 2019 |

MoE publication type | A4 Article in conference proceedings |

Event | The 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - Aachen, Germany Duration: 26 Aug 2019 → 31 Aug 2019 https://tcs.rwth-aachen.de/mfcs2019/ |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|

Publisher | Dagstuhl Publishing |

Volume | 138 |

ISSN (Electronic) | 1868-8969 |

### Fields of Science

- cs.LO
- cs.CC
- 111 Mathematics

## Cite this

Haak, A., Kontinen, J., Müller, F., Vollmer, H., & Yang, F. (2019). Counting of Teams in First-Order Team Logics. In P. Rossmanith, P. Heggernes, & J-P. Katoen (Eds.),

*44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)*(Vol. 138, pp. 19:1-19:15). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 138). https://doi.org/10.4230/LIPIcs.MFCS.2019.19