Descriptive complexity of #P functions : A new perspective

Show full item record



Permalink

http://hdl.handle.net/10138/322725

Citation

Durand , A , Haak , A , Kontinen , J & Vollmer , H 2021 , ' Descriptive complexity of #P functions : A new perspective ' , Journal of Computer and System Sciences , vol. 116 , pp. 40 - 54 . https://doi.org/10.1016/j.jcss.2020.04.002

Title: Descriptive complexity of #P functions : A new perspective
Author: Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert
Contributor: University of Helsinki, Department of Mathematics and Statistics
Date: 2021-03
Language: eng
Number of pages: 15
Belongs to series: Journal of Computer and System Sciences
ISSN: 0022-0000
URI: http://hdl.handle.net/10138/322725
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.
Subject: 111 Mathematics
Finite model theory
Arithmetic circuits
Counting classes
Skolem function
TIME
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
DHKV.pdf 230.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record