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 -