Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2016.20
URN: urn:nbn:de:0030-drops-65601
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6560/
Durand, Arnaud ; Haak, Anselm ; Kontinen, Juha ; Vollmer, Heribert
Descriptive Complexity of #AC^0 Functions
| pdf-format: |
|
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 #AC^0 appear as classes of this hierarchy. In this way, we unconditionally place #AC^0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC^0 which can be descriptively characterized as a class in our framework.
BibTeX - Entry
@InProceedings{durand_et_al:LIPIcs:2016:6560,
author = {Arnaud Durand and Anselm Haak and Juha Kontinen and Heribert Vollmer},
title = {{Descriptive Complexity of #AC^0 Functions}},
booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
pages = {20:1--20:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-022-4},
ISSN = {1868-8969},
year = {2016},
volume = {62},
editor = {Jean-Marc Talbot and Laurent Regnier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6560},
URN = {urn:nbn:de:0030-drops-65601},
doi = {10.4230/LIPIcs.CSL.2016.20},
annote = {Keywords: finite model theory, Fagin's theorem, arithmetic circuits, counting classes, Skolem function}
}
| Keywords: | finite model theory, Fagin's theorem, arithmetic circuits, counting classes, Skolem function | |
| Seminar: | 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 29.08.2016 |
