Counting of Teams in First-Order Team Logics

Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer, Fan Yang

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Kuvaus

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.
Alkuperäiskielienglanti
OtsikkoProceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Julkaisupäiväelokuuta 2019
TilaJulkaistu - elokuuta 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaThe 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - Aachen, Saksa
Kesto: 26 elokuuta 201931 elokuuta 2019
https://tcs.rwth-aachen.de/mfcs2019/

Lainaa tätä

Haak, A., Kontinen, J., Müller, F., Vollmer, H., & Yang, F. (2019). Counting of Teams in First-Order Team Logics. teoksessa Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Haak, Anselm ; Kontinen, Juha ; Müller, Fabian ; Vollmer, Heribert ; Yang, Fan. / Counting of Teams in First-Order Team Logics. Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). 2019.
@inproceedings{4798f3a8e43e4c82b7fef4f359bc2035,
title = "Counting of Teams in First-Order Team Logics",
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.",
keywords = "cs.LO, cs.CC",
author = "Anselm Haak and Juha Kontinen and Fabian M{\"u}ller and Heribert Vollmer and Fan Yang",
year = "2019",
month = "8",
language = "English",
booktitle = "Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)",

}

Haak, A, Kontinen, J, Müller, F, Vollmer, H & Yang, F 2019, Counting of Teams in First-Order Team Logics. julkaisussa Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). The 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Aachen, Saksa, 26/08/2019.

Counting of Teams in First-Order Team Logics. / Haak, Anselm; Kontinen, Juha; Müller, Fabian; Vollmer, Heribert; Yang, Fan.

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). 2019.

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

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

PY - 2019/8

Y1 - 2019/8

N2 - 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.

AB - 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.

KW - cs.LO

KW - cs.CC

M3 - Conference contribution

BT - Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

ER -

Haak A, Kontinen J, Müller F, Vollmer H, Yang F. Counting of Teams in First-Order Team Logics. julkaisussa Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). 2019