Details
| Original language | English |
|---|---|
| Pages (from-to) | 40-54 |
| Number of pages | 15 |
| Journal | Journal of Computer and System Sciences |
| Volume | 116 |
| Early online date | 30 Apr 2020 |
| Publication status | Published - Mar 2021 |
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.
Keywords
- Arithmetic circuits, Counting classes, Finite model theory, Skolem function, Fagin's theorem
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Mathematics(all)
- Applied Mathematics
- Computer Science(all)
- Computer Networks and Communications
- Computer Science(all)
- Computational Theory and Mathematics
- Computer Science(all)
- Software
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Journal of Computer and System Sciences, Vol. 116, 03.2021, p. 40-54.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Descriptive complexity of #P functions
T2 - A new perspective
AU - Durand, Arnaud
AU - Haak, Anselm
AU - Kontinen, Juha
AU - Vollmer, Heribert
N1 - Funding Information: This work is partially supported by DFG VO 630/8-1 , DAAD grant 57348395 , grants 308099 and 308712 of the Academy of Finland and grant ANR-14-CE25-0017-02 AGGREG of the ANR .
PY - 2021/3
Y1 - 2021/3
N2 - 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.
AB - 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.
KW - Arithmetic circuits
KW - Counting classes
KW - Finite model theory
KW - Skolem function
KW - Fagin's theorem
UR - http://www.scopus.com/inward/record.url?scp=85089133736&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2020.04.002
DO - 10.1016/j.jcss.2020.04.002
M3 - Article
VL - 116
SP - 40
EP - 54
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
ER -