Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 40-54 |
| Seitenumfang | 15 |
| Fachzeitschrift | Journal of Computer and System Sciences |
| Jahrgang | 116 |
| Frühes Online-Datum | 30 Apr. 2020 |
| Publikationsstatus | Veröffentlicht - März 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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Mathematik (insg.)
- Angewandte Mathematik
- Informatik (insg.)
- Computernetzwerke und -kommunikation
- Informatik (insg.)
- Theoretische Informatik und Mathematik
- Informatik (insg.)
- Software
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Journal of Computer and System Sciences, Jahrgang 116, 03.2021, S. 40-54.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -