Descriptive complexity of #P functions: A new perspective

Arnaud Durand, Anselm Haak, Juha Kontinen, Heribert Vollmer

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC0 appear as classes of this hierarchy. In this way, we unconditionally place #AC0 properly in a strict hierarchy of arithmetic classes within #P. Furthermore, we show that some of our classes admit efficient approximation in the sense of FPRAS. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. and argue that our approach is better suited to study arithmetic circuit classes such as #AC0 which can be descriptively characterized as a class in our framework.
Original languageEnglish
JournalJournal of Computer and System Sciences
Number of pages15
ISSN0022-0000
DOIs
Publication statusE-pub ahead of print - 30 Apr 2020
MoE publication typeA1 Journal article-refereed

Fields of Science

  • Finite model theory
  • Arithmetic circuits
  • Counting classes
  • Skolem function
  • 111 Mathematics

Cite this