Document Open Access Logo

Counting of Teams in First-Order Team Logics

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2019.19.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Complexity classes
  • Theory of computation → Complexity theory and logic
Keywords
  • team-based logics
  • counting classes
  • finite model theory
  • descriptive complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer, and Fan Yang. Counting of Teams in First-Order Team Logics. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.19

Author Details

Anselm Haak
  • Theoretische Informatik, Leibniz Universität Hannover, Appelstraße, D-30167, Germany
Juha Kontinen
  • Department of Mathematics and Statistics, University of Helsinki, Pietari Kalmin katu 5, 00014, Finland
Fabian Müller
  • Theoretische Informatik, Leibniz Universität Hannover, Appelstraße, D-30167, Germany
Heribert Vollmer
  • Theoretische Informatik, Leibniz Universität Hannover, Appelstraße, D-30167, Germany
Fan Yang
  • Department of Mathematics and Statistics, University of Helsinki, Pietari Kalmin katu 5, 00014, Finland

Funding

Anselm Haak, Fabian Müller, Heribert Vollmer: Supported by DFG VO 630/8-1 and DAAD grant 57348395. Juha Kontinen, Fan Yang: Supported by grants 308712 and 308099 of the Academy of Finland.

Acknowledgements

We thank the anonymous referees for helpful comments.

References

  1. Marcelo Arenas, Martin Muñoz, and Cristian Riveros. Descriptive Complexity for counting complexity classes. In LICS, pages 1-12. IEEE Computer Society, 2017. Google Scholar
  2. Rehan Abdul Aziz, Geoffrey Chu, Christian J. Muise, and Peter J. Stuckey. #∃SAT: Projected model counting. In SAT, volume 9340 of Lecture Notes in Computer Science, pages 121-137. Springer, 2015. Google Scholar
  3. Fahiem Bacchus, Shannon Dalmao, and Toniann Pitassi. Solving #SAT and Bayesian Inference with Backtracking Search. CoRR, abs/1401.3458, 2014. Google Scholar
  4. Ivano Ciardelli. Dependency as Question Entailment. In Samsom Abramsky, Juha Kontinen, Jouko Väänänen, and Heribert Vollmer, editors, Dependence Logic: Theory and Application, Progress in Computer Science and Applied Logic, pages 129-182. Birkhauser, 2016. Google Scholar
  5. Jukka Corander, Antti Hyttinen, Juha Kontinen, Johan Pensar, and Jouko Väänänen. A Logical Approach to Context-Specific Independence. Ann. Pure Appl. Logic, 2019. Google Scholar
  6. Arnaud Durand, Johannes Ebbing, Juha Kontinen, and Heribert Vollmer. Dependence Logic with a Majority Quantifier. Journal of Logic, Language and Information, 24(3):289-305, 2015. URL: https://doi.org/10.1007/s10849-015-9218-3.
  7. Arnaud Durand, Anselm Haak, Juha Kontinen, and Heribert Vollmer. Descriptive Complexity of #AC^0 Functions. In CSL, volume 62 of LIPIcs, pages 20:1-20:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  8. Arnaud Durand, Anselm Haak, and Heribert Vollmer. Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth. In LICS, pages 354-363. ACM, 2018. Google Scholar
  9. Arnaud Durand, Juha Kontinen, Nicolas de Rugy-Altherre, and Jouko Väänänen. Tractability Frontier of Data Complexity in Team Semantics. In GandALF, volume 193 of EPTCS, pages 73-85, 2015. Google Scholar
  10. Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci., 76(3-4):267-277, 2010. URL: https://doi.org/10.1016/j.jcss.2009.08.003.
  11. Ronald Fagin. Generalized first-order spectra, and polynomial time recognizable sets. SIAM-AMS Proceedings, 7:43-73, 1974. Google Scholar
  12. Pietro Galliani. Inclusion and exclusion dependencies in team semantics - On some logics of imperfect information. Ann. Pure Appl. Logic, 163(1):68-84, 2012. Google Scholar
  13. Pietro Galliani and Lauri Hella. Inclusion Logic and Fixed Point Logic. In CSL, volume 23 of LIPIcs, pages 281-295. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  14. Erich Grädel and Jouko A. Väänänen. Dependence and Independence. Studia Logica, 101(2):399-410, 2013. Google Scholar
  15. Miika Hannula, Åsa Hirvonen, Juha Kontinen, Vadim Kulikov, and Jonni Virtema. Facets of Distribution Identities in Probabilistic Team Semantics. CoRR, abs/1812.05873, 2018. Google Scholar
  16. Miika Hannula and Juha Kontinen. A finite axiomatization of conditional independence and inclusion dependencies. Inf. Comput., 249:121-137, 2016. Google Scholar
  17. Lane A. Hemaspaandra and Heribert Vollmer. The satanic notations: counting classes beyond #P and other definitional adventures. SIGACT News, 26(1):2-13, 1995. Google Scholar
  18. Tapani Hyttinen, Gianluca Paolini, and Jouko Väänänen. Quantum Team Logic and Bell’s inequalities. Rew. Symb. Logic, 8(4):722-742, 2015. URL: https://doi.org/10.1017/S1755020315000192.
  19. Neil Immerman. Relational Queries Computable in Polynomial Time. Information and Control, 68(1-3):86-104, 1986. Google Scholar
  20. Neil Immerman. Descriptive Complexity. Graduate texts in computer science. Springer, 1999. Google Scholar
  21. Juha Kontinen. A logical characterization of the counting hierarchy. ACM Trans. Comput. Log., 10(1):7:1-7:21, 2009. Google Scholar
  22. Juha Kontinen, Antti Kuusisto, and Jonni Virtema. Decidability of Predicate Logics with Team Semantics. In MFCS, volume 58 of LIPIcs, pages 60:1-60:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  23. Juha Kontinen and Hannu Niemistö. Extensions of MSO and the monadic counting hierarchy. Inf. Comput., 209(1):1-19, 2011. Google Scholar
  24. Juha Kontinen and Jouko A. Väänänen. On Definability in Dependence Logic. Journal of Logic, Language and Information, 18(3):317-332, 2009. Google Scholar
  25. Juha Kontinen and Fan Yang. Logics for first-order team properties. In WoLLIC, Lecture Notes in Computer Science. Springer, 2019. Google Scholar
  26. Antti Kuusisto. A Double Team Semantics for Generalized Quantifiers. Journal of Logic, Language and Information, 24(2):149-191, 2015. Google Scholar
  27. Antti Kuusisto and Carsten Lutz. Weighted model counting beyond two-variable logic. In LICS, pages 619-628. ACM, 2018. Google Scholar
  28. Eric Pacuit and Fan Yang. Dependence and Independence in Social Choice: Arrow’s Theorem. In H. Vollmer S. Abramsky, J. Kontinen and J. Väänänen, editors, Dependence Logic: Theory and Application, Progress in Computer Science and Applied Logic, pages 235-260. Birkhauser, 2016. Google Scholar
  29. Aris Pagourtzis and Stathis Zachos. The Complexity of Counting Functions with Easy Decision Version. In MFCS, volume 4162 of Lecture Notes in Computer Science, pages 741-752. Springer, 2006. Google Scholar
  30. Sanjeev Saluja, K. V. Subrahmanyam, and Madhukar N. Thakur. Descriptive Complexity of #P Functions. J. Comput. Syst. Sci., 50(3):493-505, 1995. Google Scholar
  31. Jouko A. Väänänen. Dependence Logic - A New Approach to Independence Friendly Logic, volume 70 of London Mathematical Society student texts. Cambridge University Press, 2007. Google Scholar
  32. Leslie G. Valiant. The Complexity of Computing the Permanent. Theor. Comput. Sci., 8:189-201, 1979. Google Scholar
  33. Leslie G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 8(3):410-421, 1979. Google Scholar
  34. Moshe Y. Vardi. The Complexity of Relational Query Languages (Extended Abstract). In STOC, pages 137-146. ACM, 1982. Google Scholar
  35. Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact